Cutting planes, branching and total unimodularity

Study notes on four questions in integer programming: what data Gomory cuts need, why Meyer’s theorem matters, how cuts compare with branch-and-bound, and when an integer program can be solved as a plain linear program.

A polygon of LP-feasible points, the smaller integer hull inside it, and a cutting plane separating them fractional LP vertex integer hull PI P cut x₁ + 2x₂ ≤ 8
The LP relaxation P (blue) is larger than the integer hull PI (green). A cutting plane (dashed) removes the fractional vertex without removing any integer point.

1Gomory cuts and the data they need

For Gomory’s pure-integer (fractional) cut, the standard assumption is that the constraint data A and b are integers. Rational data is equally acceptable, because each constraint can be multiplied by the least common multiple of its denominators to give an equivalent integer system. What the method cannot handle in general is irrational data.

Why integrality matters

The fractional cut comes from a row of the optimal simplex tableau,

xi + Σj āij xj = b̄i,

which gives the cut

Σj f(āij) xj ≥ f(b̄i),

where f(·) is the fractional part. The derivation is valid only if every variable in that row is integer-constrained, including the slack variables. If Ax ≤ b has integer A and b, then for any integer x the slack s = b − Ax is automatically an integer, so the cut is valid. If the coefficients are fractional and you don’t scale first, the slacks need not be integer for an integer x, and the cut may remove feasible integer points.

Why rational is enough but irrational isn’t

With rational data, scaling restores integer slacks and all tableau entries stay rational, so fractional parts behave well. Gomory’s 1958 finite-convergence proof applies (with lexicographic dual simplex and a suitable rule for choosing the source row), and Meyer’s theorem (Section 2) guarantees that the integer hull is a polyhedron that finitely many cuts can describe. With irrational data the slacks can’t be scaled to integers, the integer hull may not be a polyhedron, and finite convergence can fail.

The mixed-integer case

The Gomory mixed-integer (GMI) cut handles continuous variables, so slacks don’t need to be integer. It is valid as long as the integer-constrained variables really are integer. Finite convergence for the mixed-integer version, however, needs extra conditions, such as an integer-valued objective, and doesn’t hold in general.

The data should be integer for the classical method, rational is fine after scaling, and irrational coefficients break the theory.

2Meyer’s theorem

Theorem (Meyer, 1974). If P = {x ∈ ℝn : Ax ≤ b} with A and b rational, then the integer hull PI = conv(P ∩ ℤn) is a rational polyhedron. In other words, it can be written as {x : A′x ≤ b′} for some finite rational system.

Why this is not obvious

If P is bounded the result is easy: P contains finitely many integer points, and the convex hull of finitely many points is a polytope. The interesting case is an unbounded P, which contains infinitely many integer points. The convex hull of an infinite set can be badly behaved: it may not be closed, or it may need infinitely many inequalities to describe it.

Sketch of the proof

  1. By the Minkowski–Weyl theorem, P = conv{v1,…,vk} + cone{r1,…,rm}. Because the data is rational, the vi and rj can be taken rational, and each ray rj can be scaled to an integer vector.
  2. Define the bounded set Q = conv{v1,…,vk} + {Σ λj rj : 0 ≤ λj ≤ 1}. It contains only finitely many integer points.
  3. Any integer point of P can be written as an integer point of Q plus a nonnegative integer combination of the rj: split each coefficient λj into its integer and fractional parts. Because the rj are integer vectors, removing the integer parts keeps the point integral.
  4. Therefore PI = conv(Q ∩ ℤn) + cone{r1,…,rm}, a polytope plus a finitely generated cone, which is a polyhedron by Minkowski–Weyl again.

Rationality enters in step 1: a ray can be scaled to an integer vector only if its direction is rational.

The link to cutting planes

Since PI is a polyhedron, it has finitely many facets. Each facet-defining inequality is valid for every integer point of P. Adding all of them to the LP turns it into min{cx : x ∈ PI}, which has an integral optimal vertex and therefore solves the integer program. So a finite set of cuts that is “enough” always exists. Chvátal (1973, bounded case) and Schrijver (1980, general rational case) sharpened this for Gomory-type cuts: repeatedly adding all Chvátal–Gomory cuts reaches PI after finitely many rounds.

What goes wrong with irrational data

Take P = {(x, y) : x ≥ 0, 0 ≤ y ≤ √2·x}. Integer points in P have y/x < √2, and those ratios get arbitrarily close to √2 (through continued-fraction approximations) without reaching it.

The cone between the x-axis and the line y equals root two times x, with integer points close to but never on the line y = √2·x (5, 7)
Integer points in the cone 0 ≤ y ≤ √2·x, shown for x ≤ 7. The green region is the hull of these points; as x grows, its upper boundary gains more and more edges that bend toward the dashed line y = √2·x without ever reaching it.
  • The integer hull is not closed: its closure contains the ray y = √2·x, but no point of that ray other than the origin belongs to the hull.
  • Its boundary consists of infinitely many edges whose slopes creep up toward √2.
  • No finite system of linear inequalities describes it, so a cutting-plane method could keep generating new cuts forever.

Caveats

Meyer’s theorem shows only that a finite description exists. It says nothing about finding it efficiently, and PI can have exponentially many facets. Gomory’s algorithm usually doesn’t need the whole hull, only enough cuts near the optimum to make the LP optimum integral. And the finite termination of Gomory’s method is a separate result that relies on specific pivoting and row-selection rules, not on Meyer’s theorem alone.

3Gomory cuts or branch-and-bound?

Neither dominates in practice. Modern solvers such as CPLEX, Gurobi, SCIP and HiGHS use branch-and-cut, which combines both because each covers the other’s weaknesses.

Pure Gomory cutting planesBranch-and-bound
IdeaSolve one LP and keep tightening it with cuts; never split the problem.Split on a fractional variable (xj ≤ ⌊v⌋ or xj ≥ ⌈v⌉) and prune subproblems by their LP bounds.
StrengthsEach cut improves the bound for the whole problem; no search tree, so little memory; finite termination with rational data and lexicographic rules.Numerically robust (only variable bounds change); finds feasible integer solutions along the way; handles general MIPs naturally.
WeaknessesTailing off: later cuts get shallower and progress stalls. Numerical instability from dense cuts with extreme coefficients. No integer solution until the very end.The tree can grow exponentially when the LP relaxation is weak, because bounds prune little.
Stopping earlyGives a bound but no usable solution.Gives a solution and a provable optimality gap.

When each tends to do better

Cutting planes are especially valuable when the LP relaxation is weak but has structure that cuts can exploit (knapsack constraints, set packing, flow conservation, lot-sizing), and when a few rounds of cuts at the root node close most of the gap, shrinking the later search tree.

Branch-and-bound alone is often enough when the LP relaxation is already tight (as in well-formulated scheduling or assignment problems), when a good feasible solution matters more than proven optimality, or when the problem is small enough that the tree stays manageable.

Why branch-and-cut wins

Balas, Ceria, Cornuéjols and Natraj (1996) showed that Gomory mixed-integer cuts, used in limited rounds inside branch-and-bound, are highly effective. That reversed the long-held view that Gomory cuts were impractical. The modern recipe is to add several rounds of cuts at the root (GMI cuts alongside cover, flow-cover and other families) until progress tails off, then branch, optionally adding more cuts at some nodes, while managing cuts carefully: limiting their number, discarding nearly parallel or numerically poor ones, and removing inactive cuts.

Solver benchmarks have shown that turning off cutting planes typically slows solvers by large factors, and turning off branching makes many problems unsolvable. GMI cuts are usually reported among the most useful single cut families.

Use cuts to tighten the relaxation, especially at the root, and use branching to finish the job. If you must pick one method alone, branch-and-bound is the more reliable default; pure Gomory cutting is mainly of theoretical and historical interest.

4Totally unimodular matrices

Total unimodularity is the main reason some integer programs are easy: you can drop the integrality constraints, solve the LP relaxation, and get an integer optimal solution with no cuts and no branching.

Definitions

  • A matrix A is totally unimodular (TU) if every square submatrix has determinant 0, +1 or −1. In particular every entry is 0 or ±1.
  • An integer m × n matrix A of full row rank is unimodular if every m × m basis matrix B has determinant ±1.

TU is the stronger and more commonly used property, suited to inequality constraints. Unimodularity is the natural condition for equality-form constraints.

The key theorems

Hoffman–Kruskal (1956). If A is TU and b is integer, every vertex of P = {x : Ax ≤ b, x ≥ 0} is integral. Conversely, if P is integral for every integer b, then A is TU.

Veinott–Dantzig (1968). For integer A of full row rank, {x : Ax = b, x ≥ 0} is integral for every integer b if and only if A is unimodular.

The proof idea is Cramer’s rule. A vertex is xB = B−1b for some basis B, and B−1 = adj(B)/det(B). The adjugate has integer entries because B does, and det(B) = ±1, so B−1 is an integer matrix and xB is integer.

Why this matters for solving IPs

Since the simplex method returns an optimal vertex, an IP with a TU constraint matrix and integer right-hand side can be solved as an ordinary LP. LP is solvable in polynomial time (ellipsoid and interior-point methods), so these IPs are polynomially solvable even though general IP is NP-hard. The dual LP also has a TU matrix (the transpose of a TU matrix is TU), so with an integer objective c the dual has an integral optimum too. This is the source of many classical min–max theorems.

Recognizing a TU matrix

  • Incidence matrices of directed graphs (each column has one +1 and one −1) are TU; these give network flow problems.
  • Incidence matrices of bipartite graphs (each column has two 1s, one in each part) are TU.
  • Interval matrices, with the consecutive-ones property in each column or each row, are TU.
  • Network matrices are TU and generalize both directed-graph incidence matrices and interval matrices.
  • Ghouila-Houri’s criterion is an exact characterization: A is TU if and only if every subset of rows can be split into two groups whose sums differ by a vector with entries in {0, ±1}.
  • Seymour’s decomposition theorem (1980) shows that every TU matrix is built from network matrices, their transposes and two special 5 × 5 matrices, which yields a polynomial-time recognition algorithm.

TU is preserved by transposition, negating rows or columns, appending identity columns (slack variables), and duplicating rows or columns.

Classic applications

  • Assignment and bipartite matching. The LP relaxation gives integer assignments, and duality gives König’s theorem: in a bipartite graph, maximum matching size equals minimum vertex cover size.
  • Transportation problems. With integer supplies and demands there is an integer optimal shipment plan.
  • Minimum-cost flow, maximum flow and shortest paths. Duality gives the max-flow min-cut theorem, and integer capacities admit an integer maximum flow.
  • Scheduling with consecutive time windows. Shift-staffing models where each shift covers a contiguous block of hours have interval matrices, and many can be reformulated as network flows.

Uses beyond solving the problem directly

  • Formulation choice. Modeling a problem so its matrix is TU, or as a network flow, avoids integer programming entirely.
  • Lagrangian relaxation. Relaxing the complicating constraints can leave a TU subproblem that is fast to solve. The catch is that the Lagrangian bound then equals the LP bound, so it doesn’t improve on the LP relaxation.
  • Decomposition methods. In column generation, pricing subproblems are often shortest-path or matching problems with TU structure.
  • Inside branch-and-bound. A large TU substructure keeps the LP relaxation tight and the search tree small, even when the full problem isn’t TU.

Limitations

TU is fragile. A single side constraint can destroy it: a shortest-path problem with an extra resource or budget constraint becomes the NP-hard constrained shortest-path problem. Matching in non-bipartite graphs isn’t TU either; for a triangle, the LP relaxation has the fractional vertex xe = ½ on every edge. Edmonds fixed this with odd-set (“blossom”) inequalities.

That fix points to a broader idea. TU is a property of the matrix alone, for every integer right-hand side. Total dual integrality (TDI), introduced by Edmonds and Giles, is a weaker, system-specific property that still guarantees integral polyhedra, and it covers cases such as general matching and matroid intersection that TU doesn’t.

5References

These references were compiled from memory without database access. Please verify volume, page and year details against the original sources before citing them.

Cutting planes and integer hulls

  1. Gomory, R. E. (1958). Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society, 64(5), 275–278.
  2. Gomory, R. E. (1960). An algorithm for the mixed integer problem. Research Memorandum RM-2597, RAND Corporation.
  3. Chvátal, V. (1973). Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics, 4(4), 305–337.
  4. Meyer, R. R. (1974). On the existence of optimal solutions to integer and mixed-integer programming problems. Mathematical Programming, 7, 223–235.
  5. Schrijver, A. (1980). On cutting planes. Annals of Discrete Mathematics, 9, 291–296.
  6. Balas, E., Ceria, S., Cornuéjols, G., & Natraj, N. (1996). Gomory cuts revisited. Operations Research Letters, 19(1), 1–9.

Branch-and-bound and computational practice

  1. Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
  2. Bixby, R., & Rothberg, E. (2007). Progress in computational mixed integer programming: a look back from the other side of the tradeoff. Annals of Operations Research, 149, 37–41.
  3. Bixby, R. E. (2012). A brief history of linear and mixed-integer programming computation. Documenta Mathematica, Extra Volume ISMP, 107–121.
  4. Achterberg, T. (2007). Constraint Integer Programming. PhD thesis, Technische Universität Berlin.

Total unimodularity and integral polyhedra

  1. Hoffman, A. J., & Kruskal, J. B. (1956). Integral boundary points of convex polyhedra. In H. W. Kuhn & A. W. Tucker (Eds.), Linear Inequalities and Related Systems (Annals of Mathematics Studies 38), 223–246. Princeton University Press.
  2. Ghouila-Houri, A. (1962). Caractérisation des matrices totalement unimodulaires. Comptes Rendus de l’Académie des Sciences, 254, 1192–1194.
  3. Edmonds, J. (1965). Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards, 69B, 125–130.
  4. Veinott, A. F., & Dantzig, G. B. (1968). Integral extreme points. SIAM Review, 10(3), 371–372.
  5. Edmonds, J., & Giles, R. (1977). A min-max relation for submodular functions on graphs. Annals of Discrete Mathematics, 1, 185–204.
  6. Seymour, P. D. (1980). Decomposition of regular matroids. Journal of Combinatorial Theory, Series B, 28(3), 305–359.

Textbooks

  1. Schrijver, A. (1986). Theory of Linear and Integer Programming. Wiley.
  2. Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley.
  3. Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). Integer Programming. Graduate Texts in Mathematics 271, Springer.
  4. Wolsey, L. A. (2020). Integer Programming (2nd ed.). Wiley.