Integer Programming: Branch-and-Bound, Gomory Cuts, Lift-and-Project, and Solver Internals

2020-02-23 · Leonardo Benicio

Summary

An inside look at integer programming algorithms—branch-and-bound, cutting planes, lift-and-project hierarchies—and how Gurobi and CPLEX solve NP-hard problems.

Integer programming (IP) is the most powerful and most dangerous tool in the optimization toolbox. An integer program is a linear program with integrality constraints: some variables must take integer values. Formally:

[ \min_x c^\top x \quad \text{s.t.} \quad Ax \leq b, \quad x \in \mathbb{Z}^p \times \mathbb{R}^{n-p} ]

The problem is NP-hard in general—SAT, TSP, Vertex Cover, and thousands of other NP-complete problems reduce to IP with a polynomial number of variables and constraints. Yet IP is the dominant modeling framework for practical combinatorial optimization: airline crew scheduling, vehicle routing, supply chain optimization, and portfolio management are routinely formulated as integer programs and solved to optimality for industrial-scale instances.

The miracle is that IP solvers (Gurobi, CPLEX, SCIP, HiGHS) routinely solve instances with millions of variables and constraints to provable optimality, despite IP being NP-hard. How? Through a sophisticated combination of linear programming relaxation, branch-and-bound, cutting planes, presolve, and primal heuristics that exploit the structure of the constraint matrix. This post opens the black box of IP solvers, explaining the algorithmic machinery that makes the impossible possible.

1. LP Relaxation and the Branch-and-Bound Tree

The starting point is the LP relaxation: ignore the integrality constraints and solve the resulting LP. The LP solution provides a lower bound for minimization—the optimal integer solution cannot be better than the LP optimum. If the LP solution happens to be integer, it is optimal for the IP and we are done. Otherwise, we must “branch”: choose a variable with fractional value in the LP solution and create two subproblems, one with (x_i \leq \lfloor v \rfloor) and one with (x_i \geq \lceil v \rceil).

Branching splits the feasible region into two disjoint parts, each of which is processed recursively. This yields a branch-and-bound tree where each node corresponds to a subproblem (an LP with additional bounds). As we descend the tree, lower bounds increase (more constraints mean a potentially higher LP optimum). If a node’s lower bound exceeds the best known integer solution (the incumbent upper bound), that node can be pruned—no integer solution within it can beat the incumbent.

The efficiency of branch-and-bound depends on three factors: (1) a tight LP relaxation that gives strong lower bounds, enabling early pruning; (2) good branching decisions that quickly improve bounds and find feasible solutions; and (3) heuristics that find good integer solutions early. Modern solvers spend enormous engineering effort on variable selection (which fractional variable to branch on), node selection (which subproblem to process next), and feasibility heuristics (rounding, diving, local search on fractional solutions).

2. Cutting Planes and Gomory's Fractional Cuts

Cutting planes strengthen the LP relaxation by adding valid inequalities—linear constraints satisfied by all integer solutions but violated by the current fractional LP solution. A cut “cuts off” the fractional point, tightening the relaxation and potentially making the LP solution integer.

Gomory fractional cuts (1958) are the classic family of general-purpose cutting planes. Given a row of the optimal simplex tableau corresponding to a basic variable with a fractional right-hand side:

[ xi + \sum{j \in NB} a_{ij} x_j = b_i ]

where (bi) is fractional. Write (a{ij} = \lfloor a*{ij} \rfloor + f*{ij}) and (bi = \lfloor b_i \rfloor + f_i), where (0 \leq f{ij}, f_i < 1). The Gomory cut is:

[ \sum*{j \in NB} f*{ij} x_j \geq f_i ]

This cut is valid (satisfied by all integer solutions) and cuts off the current fractional LP solution (where all non-basic variables are zero, the left-hand side is 0, but (f_i > 0)). Gomory cuts generated from all fractional rows and added to the LP yield a tighter relaxation; the process can be iterated—a “cut loop”—until the LP solution becomes integer or no more cuts can be generated.

The discovery that Gomory cuts, when used aggressively, could solve IPs without branching (a pure cutting-plane algorithm) was a major surprise. Balas, Ceria, Cornuéjols, and Natraj (1996) showed that the “lift-and-project” cutting planes, combined with a carefully designed branching strategy, dramatically reduce the size of the branch-and-bound tree.

3. The Lift-and-Project Hierarchy

The lift-and-project method (Balas, Ceria, Cornuéjols, 1994) systematizes the generation of strong cutting planes. Given a 0-1 integer program, the method “lifts” the problem to a higher-dimensional space where the convex hull of integer solutions is easier to describe, generates cutting planes in that space, and “projects” them back to the original space.

Concretely, consider a single variable (x_j \in {0, 1}). The LP relaxation allows (0 \leq x_j \leq 1). The lift-and-project operation constructs the disjunctive program: either (x_j = 0) or (x_j = 1). The convex hull of the union of the two feasible sets (one with (x_j = 0), one with (x_j = 1)) is the smallest convex set containing all integer solutions. The cutting planes that define this convex hull are the lift-and-project cuts for variable (x_j).

The lift-and-project hierarchy iterates this process. At level (k), it considers all subsets of (k) variables and generates cuts from the disjunction over all (2^k) assignments. The level-1 closure (cuts from individual variables) already captures many strong inequalities; the level-(n) closure is the convex hull of all integer solutions. In practice, solvers use level-1 lift-and-project cuts selectively for fractional variables, combined with Gomory mixed-integer cuts, to achieve a tight relaxation.

4. Presolve, Heuristics, and the Modern Solver Architecture

A modern IP solver’s workflow is a carefully orchestrated symphony of techniques:

Presolve: Before the LP is even solved, presolve reduces the problem. For IP, presolve is more aggressive than for LP: it tightens bounds based on integrality (e.g., if a 0-1 variable’s LP bound is [0.2, 0.8], clamp to [0, 1]), fixes variables by dominance, identifies logical implications, and detects small independent subproblems that can be solved exactly.
Root node processing: The LP relaxation is solved. Then a “cut loop” generates Gomory, lift-and-project, and problem-specific cuts (clique cuts, implied bound cuts, flow cover cuts) until no more improvements or a time limit. The root node lower bound is the foundation of the entire tree search.
Heuristics: Primal heuristics try to find good integer solutions from the fractional LP solution. “Rounding” heuristics simply round fractional values and check feasibility. “Diving” heuristics perform a mock depth-first search, branching and re-solving LPs, hoping to hit an integer solution. “RINS” (Relaxation Induced Neighborhood Search) and “Local Branching” fix most variables at their values in a known integer solution and solve a smaller IP to find improvements.
Branch-and-cut: The main tree search. Each node solves an LP relaxation (warm-started from the parent node’s optimal basis). If the solution is fractional and the lower bound is below the incumbent, generate additional cutting planes specific to this node (“local cuts”), then branch. The cut loop at each node is limited (often 1-2 rounds) to keep nodes cheap.
Conflict analysis: When a node is infeasible or pruned, the solver analyzes the conflict—the set of bound changes that led to the infeasibility—and generates “conflict constraints” that prevent the same dead-end from being explored elsewhere in the tree.

5. Symmetry Breaking and Orbital Branching

Integer programs often have symmetry: permuting variables yields equivalent solutions. For example, in graph coloring, permuting colors yields an equivalent coloring. Symmetry causes branch-and-bound to explore exponentially many symmetric solutions, destroying performance. Symmetry breaking adds constraints that eliminate symmetric copies while preserving at least one optimal solution.

Orbital branching (Ostrowski, Linderoth, Rossi, Smriglio, 2011) is the state-of-the-art approach. It computes the symmetry group of the IP (using graph automorphism tools like Nauty or Bliss) and tracks the orbits of variables—sets of variables that can be permuted into each other. When branching on a variable, orbital branching fixes not just that variable but its entire orbit, breaking symmetry aggressively. This can reduce the search tree from exponential to manageable size.

6. Summary

Integer programming solvers are the most sophisticated optimization engines ever built, combining LP relaxation, cutting planes (Gomory, lift-and-project), branch-and-bound, presolve, heuristics, and symmetry breaking into an integrated system. The result is a tool that routinely solves NP-hard optimization problems of industrial scale to provable optimality. The gap between the theoretical intractability of IP and its practical solvability is one of the great stories of operations research—a testament to the power of engineering, algorithmic insight, and the hidden structure of real-world combinatorial problems.

7. Decomposition Methods in Integer Programming

Large-scale integer programs often have a decomposable structure that can be exploited. Dantzig-Wolfe decomposition for IP, mentioned earlier in the context of LP, extends to IP via branch-and-price: a branch-and-bound tree where each node solves an LP via column generation. The columns in the master problem correspond to integer solutions of subproblems, and branching must be done carefully to preserve the column generation structure.

Benders decomposition for mixed-integer programming separates the integer variables (assigned in the master problem) from the continuous variables (optimized in the subproblem). The subproblem generates Benders cuts—linear inequalities that approximate the value function of the continuous part—which are added to the master problem. Benders decomposition is the engine behind stochastic mixed-integer programming solvers and many industrial supply chain optimization systems.

Lagrangian relaxation (Geoffrion, 1974) dualizes complicating constraints, replacing them with penalty terms in the objective. The Lagrangian dual is a convex optimization problem whose solution provides a lower bound on the optimal IP value. Lagrangian relaxation is particularly effective when the remaining constraints form a tractable subproblem (e.g., a shortest path, a spanning tree, or an assignment problem). The subgradient method or the bundle method solves the Lagrangian dual, and the resulting solution can be “repaired” to obtain a feasible IP solution via heuristics.

8. The Art of IP Modeling: Strong Formulations and Ideal Formulations

The computational performance of an IP solver depends critically on the formulation—how the combinatorial problem is expressed as integer linear constraints. A “strong” formulation has a tight LP relaxation: the LP optimum is close to the IP optimum. The strongest possible formulation is an “ideal” formulation: the LP relaxation exactly describes the convex hull of integer solutions.

For the traveling salesman problem, the subtour elimination constraints (there are exponentially many) yield a very strong formulation; the LP relaxation typically gives a lower bound within 1-2% of the optimal tour length. For the uncapacitated facility location problem, the “strong” formulation (with exponentially many constraints linking opening decisions to service assignments) has an integral LP relaxation—solving the LP automatically yields an integer optimal solution, so no branching is needed.

The modeler’s craft is to find the right formulation—one that is strong enough to be solvable but not so large that the LP becomes intractable. This involves adding valid inequalities that “cut off” fractional solutions, choosing between big-M and indicator constraints for logical conditions, and exploiting symmetry-breaking inequalities. The best formulations are often discovered through a combination of theoretical analysis (polyhedral combinatorics) and computational experimentation (solving test instances and inspecting the LP solutions).

9. Quantum Integer Programming and the Future

Quantum computing, while in its infancy, has potential implications for integer programming. Grover’s search algorithm can speed up the search for solutions in a branch-and-bound tree, offering a quadratic speedup for exhaustive search. Quantum annealing (D-Wave systems) directly solves quadratic unconstrained binary optimization (QUBO) problems, a special class of IPs. The quantum approximate optimization algorithm (QAOA) provides heuristic solutions for combinatorial optimization problems on near-term quantum devices.

However, the consensus among optimization researchers is that quantum computers, even when fault-tolerant and large-scale, will not render IP solvers obsolete. The exponential speedup of Shor’s algorithm for factoring does not extend to general IP; the best known quantum algorithms for IP achieve only polynomial speedups over classical algorithms (Grover-type). The real future of IP solving likely involves hybrid classical-quantum architectures where classical solvers handle presolve, cutting planes, and primal heuristics, while quantum subroutines accelerate specific subproblems (eigenvalue computations for SDP-based cuts, Grover search for primal heuristics).

For further reading, Wolsey’s “Integer Programming” (1998) is the classic introduction. Conforti, Cornuéjols, and Zambelli’s “Integer Programming” (2014) provides a modern, rigorous treatment. Achterberg’s Ph.D. thesis on SCIP details the architecture of a modern constraint integer programming solver. The Gurobi and CPLEX user manuals are treasure troves of practical modeling advice. The reader is encouraged to formulate a small TSP or scheduling problem as an IP and solve it with an open-source solver—the experience of watching branch-and-bound prune the search tree is the best introduction to the magic of integer programming.

10. Recent Advances: Learning-Based Branching and Neural Combinatorial Optimization

The choice of which variable to branch on has historically been guided by heuristics (strong branching, pseudocost branching, reliability branching). Recent work applies machine learning to learn branching strategies. Khalil, Le Bodic, Song, Nemhauser, and Dilkina (2016) used imitation learning: train a neural network to mimic the branching decisions of strong branching (which is expensive but effective), then use the learned policy at scale. The resulting “learned branching” matches or exceeds expert-designed heuristics and adapts to the distribution of problem instances.

More ambitiously, neural combinatorial optimization aims to solve IPs directly using deep learning. Pointer networks (Vinyals, Fortunato, Jaitly, 2015) and graph neural networks (Gasse, Chételat, Ferroni, Charlin, Lodi, 2019) learn to construct feasible solutions by sequentially selecting variables. While these learned heuristics do not provide optimality guarantees, they can rapidly produce high-quality solutions that serve as warm starts for exact solvers, reducing solve times significantly.

Reinforcement learning has also been applied to cut selection: which of the many generated cuts to add to the LP relaxation? Baltean-Lugojan, Misener, and Bonami (2019) used deep reinforcement learning to select a small, effective set of cuts, outperforming traditional density-based cut selection. The integration of machine learning into integer programming solvers is an active and rapidly growing area, combining the reliability of combinatorial optimization with the adaptability of data-db7735b methods.

11. The Future: Quantum IP Solvers and Hardware Acceleration

Quantum computing offers a potential exponential speedup for certain subroutines in IP solving. Grover’s algorithm can search an unstructured space of size N in O(√N) time, compared to O(N) classically. In the context of IP, this could accelerate primal heuristics (finding good integer solutions by quantum search over the feasible region) and the exploration of alternative branches in branch-and-bound.

However, the quadratic speedup of Grover’s algorithm does not convert an exponential-time algorithm into a polynomial-time one: if the classical algorithm takes 2^n time, the quantum version still takes 2^{n/2} time—exponential, albeit with a halved exponent. For IP, where the worst-case complexity is believed to be exponential, quantum computing offers a constant-factor speedup in the exponent, not a polynomial solution.

FPGA and GPU acceleration of IP solvers is more immediately practical. The LP relaxation solves at each node—a matrix factorization followed by triangular solves—can be offloaded to GPUs, achieving significant speedups for large, dense LPs. Custom FPGA implementations of the simplex method and interior-point methods have been demonstrated, offering lower latency and higher throughput for specific problem classes. The future of IP solving is likely heterogeneous: CPUs for branch-and-bound control, GPUs for linear algebra, and FPGAs for specialized acceleration of cut generation and primal heuristics.

12. Summary

13. Summary and Further Perspectives

The art of IP modeling is as important as the solver itself. A poorly formulated IP may have a weak LP relaxation, leading to an enormous branch-and-bound tree. A clever formulation—with tight bounds, symmetry breaking constraints, and problem-specific cutting planes—can make the difference between solving in seconds and never solving at all. The IP modeler’s maxim: the best algorithm is a better formulation. The frontiers—decomposition methods, learning-based branching, neural combinatorial optimization, and quantum acceleration—promise to extend the reach of IP solvers even further.

14. Integer Programming and the Theory of Extended Formulations

Integer programming is intimately connected to the theory of extended formulations, discussed in an earlier post on linear programming. The convex hull of integer solutions to an IP—the “integer hull”—can sometimes be described by a compact extended formulation (an LP in a higher-dimensional space that projects onto the integer hull). For matching, the Edmonds polytope has a compact extended formulation. For spanning trees, the spanning tree polytope has one. For TSP, it does not (Yannakakis, 1991; Fiorini et al., 2012).

The non-existence of compact extended formulations for NP-hard problems explains why branch-and-cut is necessary: the integer hull is intrinsically complex, and no polynomial-size LP can capture it exactly. Cutting planes (Gomory, lift-and-project) are iterative procedures that approximate the integer hull from the outside, and branch-and-bound handles what the cuts cannot capture. The extended formulation lower bounds provide a theoretical explanation for the empirical observation that some IPs require large branch-and-bound trees.

15. The Symbiosis of Theory and Practice in Integer Programming

Integer programming is a triumph of the symbiosis between theory and practice. Theoretical advances (cutting planes, lift-and-project, decomposition methods) are rapidly incorporated into solvers and tested on industrial benchmarks. Practical observations (the effectiveness of certain cut families, the behavior of branching heuristics) inspire theoretical investigations that explain why they work. The annual MIPLIB benchmark library and the DIMACS implementation challenges drive this virtuous cycle.

The future of IP solving lies in the integration of machine learning, quantum computing, and specialized hardware acceleration. Neural branching policies, learned cut selection, and quantum subroutines for primal heuristics are active research areas. But the core of IP solving—the branch-and-cut framework, the LP relaxation, the cutting plane loop—will remain the algorithmic backbone for the foreseeable future. The combination of deep theoretical understanding and relentless engineering optimization that characterizes modern IP solvers is a model for how to attack NP-hard problems in practice.

16. Conclusion

Integer programming is the most successful approach to solving NP-hard optimization problems in practice. The branch-and-cut framework, combining LP relaxation, cutting planes, and branch-and-bound, leverages the efficiency of linear programming to explore the space of integer solutions. Modern solvers routinely solve industrial-scale instances to provable optimality, despite the theoretical intractability of IP. The art of IP modeling—choosing the right formulation, adding the right cuts, exploiting structure—is as important as the solver itself. The field continues to evolve, driven by the practical need to solve ever-larger and more complex optimization problems.

17. Integer Programming and Machine Learning: A Two-Way Street

The relationship between integer programming and machine learning is bidirectional. Machine learning aids IP solving: neural branching policies, learned cut selection, and reinforcement learning for primal heuristics improve solver performance. IP aids machine learning: decision trees, rule lists, and sparse neural networks can be trained via integer programming formulations that yield provably optimal models.

Optimal decision trees—trees that minimize training error subject to a depth constraint—can be formulated as IPs (Bertsimas and Dunn, 2017). The IP formulation has variables for each node (which feature to split on, which threshold to use) and constraints ensuring the tree structure. While the IP is NP-hard, modern solvers can find optimal trees for medium-sized datasets, providing a benchmark against which greedy heuristics (CART, C4.5) can be compared. The IP formulation can incorporate fairness constraints (e.g., the tree must achieve equal accuracy across demographic groups), yielding “fair decision trees” with provable guarantees.

18. The Future of Optimization: Integration and Automation

The future of optimization—integer programming, convex optimization, and machine learning—is integration. Automated Machine Learning (AutoML) systems use IP and Bayesian optimization to select model architectures and hyperparameters. Differentiable programming embeds optimization problems as layers in neural networks. And neural combinatorial optimization uses deep learning to solve IPs directly. The boundaries between optimization, machine learning, and artificial intelligence are dissolving, and the resulting synthesis promises to make optimization more accessible, more powerful, and more widely applied.

19. Conclusion

Integer programming solvers represent the pinnacle of optimization engineering, combining decades of theoretical advances (cutting planes, branch-and-bound, presolve) with relentless performance optimization to solve NP-hard problems at industrial scale. The art of IP modeling—formulating a combinatorial problem as integer linear constraints that a solver can handle—is as important as the solver itself. The integration with machine learning and the prospects of quantum acceleration point toward an exciting future for integer programming.

20. The Craft and Science of Integer Programming

Integer programming is both a craft and a science. The science is the theory we have discussed: LP relaxation, cutting planes, branch-and-bound, extended formulations, and complexity lower bounds. The craft is the art of modeling: translating a business problem into variables, constraints, and an objective that a solver can handle. A skilled IP modeler knows that the “obvious” formulation may have a weak LP relaxation, that adding redundant constraints can strengthen the relaxation, that symmetry must be broken, and that the choice between a “big-M” and an “indicator” constraint can determine success or failure.

The IP modeling process is iterative: formulate, solve, inspect the LP solution, add cuts, reformulate, repeat. The solver’s log—the sequence of lower bounds, upper bounds, nodes explored, and cuts added—is a narrative of the search for optimality. Reading this log is like reading a detective story: the solver probes the feasible region, discovers its structure, and gradually narrows the gap between the best known solution and the best possible bound. When the gap closes to zero, the mystery is solved—the solution is provably optimal.

21. Conclusion: The Enduring Magic of Integer Programming

Integer programming is magic. You describe a combinatorial optimization problem in a formal language (variables, constraints, objective), hand it to a solver, and—sometimes, for problems with millions of variables—it returns a provably optimal solution. The fact that this works at all, given the NP-hardness of IP, is astonishing. The fact that it works routinely for industrial-scale problems in logistics, finance, manufacturing, and telecommunications is a triumph of human ingenuity.

The magic is the result of decades of algorithmic research: Dantzig’s simplex method, Gomory’s cutting planes, Land and Doig’s branch-and-bound, Balas’s lift-and-project, and the modern synthesis of all these ideas into commercial solvers. The magic is also the result of Moore’s law, which has multiplied computational power by a factor of billions. But the deepest magic is mathematical: the structure of integer programs—the geometry of the integer hull, the algebra of cutting planes, the combinatorics of branching—is so rich that solvers can exploit it to solve problems that are, in theory, intractable. This gap between theory and practice is not a failure of theory but an invitation to deeper understanding.

22. Learning from the Masters: Computational Experience in Integer Programming

The lore of integer programming is passed down through computational experience. The masters of the craft—Bob Bixby (founder of CPLEX), Zonghao Gu and Ed Rothberg (founders of Gurobi), and the late Egon Balas (father of disjunctive programming)—have distilled decades of experience into the heuristics that make modern solvers fast. Some lessons from the masters:

First, presolve is everything. A surprising fraction of IPs submitted to solvers are “easy” after presolve reduces them to triviality. Second, cuts are powerful but must be used judiciously: too many cuts slow down the LP solves; too few fail to tighten the relaxation. The art is in the balance. Third, branching on the most fractional variable is surprisingly effective; sophisticated branching rules (strong branching, pseudocost, reliability branching) are only marginally better for most instances. Fourth, primal heuristics are the unsung heroes: finding a good feasible solution early prunes vast swaths of the branch-and-bound tree. Fifth, numerical stability is a constant battle: ill-conditioned bases, near-zero pivots, and accumulated rounding errors can derail the solver. The engineering of IP solvers is as much about numerical analysis as about combinatorial optimization.

23. Conclusion: The Magic and the Craft

Integer programming is both magic and craft. The magic is that NP-hard problems of industrial scale can be solved to provable optimality. The craft is the decades of theoretical development and engineering optimization that make this possible. The LP relaxation, cutting planes, branch-and-bound, presolve, heuristics, and symmetry breaking are the components; the solver integrates them into a symphony of optimization. The modeler’s art—formulating the problem, choosing the right constraints, providing initial solutions—is the conductor. Together, they produce results that seem to defy the theoretical intractability of IP.

The future promises even greater magic: machine learning for branching and cut selection, quantum algorithms for primal heuristics, and specialized hardware for LP solves. But the core of integer programming—the branch-and-cut framework, the duality between cuts and branching, the geometry of the integer hull—will remain the foundation. Integer programming is a triumph of the human intellect, a tool that extends our ability to reason about and optimize complex systems far beyond what unaided intuition can achieve.

The integration of cutting planes and branch-and-bound—“branch-and-cut”—is the algorithmic innovation that makes modern IP solvers so effective. Without cuts, branch-and-bound trees explode exponentially. Without branching, pure cutting-plane algorithms stall after generating thousands of cuts with diminishing returns. The synergy: cuts tighten the LP relaxation at the root node, reducing the size of the subsequent tree; branching handles what cuts cannot; and the cut loop at each node generates cuts tailored to the specific subproblem. Gomory mixed-integer cuts, generated from the rows of the optimal simplex tableau, are the workhorse; lift-and-project cuts and clique cuts provide additional strength for specific structures. The branch-and-cut framework, pioneered by Grötschel, Jünger, and Reinelt in the 1980s for the TSP and generalized by Padberg, Rinaldi, and Balas, is the foundation on which all modern IP solvers are built.