Cutting Planes

You want to schedule shifts, load trucks, or allocate frequencies — problems where the answer must be whole numbers: you can't hire half a worker or use 2.7 radio channels. The natural mathematical tool is integer programming (IP), which looks exactly like a linear program except every variable must be an integer.

The catch: linear programs are easy (polynomial time, solved by the simplex method or interior-point methods), while integer programs are NP-hard in general — see the integer programming article. The gap between the two lives in the LP relaxation: drop the integrality requirement, solve the easier LP, and you usually get a fractional answer like x = 2.7 that you can't directly use.

Cutting planes are the classical fix. Each cut is a new linear inequality that is valid for every integer-feasible point (it does not remove any integer solution) but invalid for the current fractional LP optimum (it chops that point off). Add enough cuts and the LP optimum is forced to land on an integer point — no branch-and-bound search required, at least in principle.

Ralph Gomory invented a systematic way to generate such cuts in 1958, and his Gomory cuts remain inside every commercial mixed-integer programming (MIP) solver to this day. The idea is elegant: stare at a single row of the simplex tableau, round down every fractional coefficient, and read off an inequality that every integer solution must obey.

The demo below shows a tiny integer program in two variables. The shaded region is the LP relaxation feasible set; the star marks its fractional optimum. Press Add Gomory Cut to add one cutting-plane inequality. Each cut slices off the current fractional optimum while leaving all integer points intact. Keep cutting until the LP optimum lands on an integer point.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="320" height="300"></canvas>
<div class="info" id="info"></div>
<div class="btns">
  <button id="cut" type="button">{{btn_add_cut}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; display: block; max-width: 100%; }
.info { font-size: .9rem; min-height: 2.8em; margin: .5rem 0; line-height: 1.5; }
.info .ok  { color: #0a7d33; font-weight: 700; }
.info .cut { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what happens: each cut is a perfectly valid constraint for integers — no integer lattice point inside the original region is ever removed. Yet each cut chips away at the fractional corner until only an integer solution survives. This is the genius of the method: validity is guaranteed by arithmetic, and progress toward integrality is guaranteed by the structure of the simplex tableau.

Gomory proved in 1958 that his cuts always converge: for any IP with a bounded feasible region, finitely many Gomory cuts reduce the LP relaxation to exactly the integer hull (the convex hull of all integer-feasible points). Once the LP relaxation is the integer hull, its optimum is automatically integer.

But the theory has a dark side:

• Exponential worst case. The number of cuts needed to reach the integer hull can be exponential in the problem size. Chvátal (1973) and later Gomory himself formalized this: the Chvátal rank of a polyhedron measures how many rounds of rounding are needed, and it can be arbitrarily large.
• IP is still NP-hard. No cutting-plane algorithm sidesteps this — a polynomial-time cutting-plane algorithm for general IP would imply P = NP, touching the deepest open question in P vs NP.
• Separation is the bottleneck. To add a cut you first need to find a violated inequality; for general cut families, that separation problem is itself NP-hard.

In practice, the picture is far brighter. Modern MIP solvers (CPLEX, Gurobi, SCIP) combine a handful of Chvátal-Gomory rounds with specialized cuts (knapsack covers, clique cuts, mixed-integer rounding cuts) plus branch and bound. For the industrial problems that matter — scheduling, logistics, network design — this hybrid routinely solves instances with millions of variables.

The status: solved as a practical technique (Gomory, 1958; production MIP solvers since the 1990s), but the worst-case complexity of integer programming remains NP-hard and the theory of cutting-plane proof systems is an active research frontier.

Cutting planes are not a theoretical curiosity — they are the engine inside the solvers that run the modern economy:

• Airline crew and fleet scheduling: assigning thousands of crew members to flights while satisfying union rules is a massive set-partitioning IP. Gomory cuts and specialized column-generation schemes make these problems tractable overnight.
• Chip design and VLSI routing: placing gates and routing wires on a silicon die involves huge binary programs. Cutting planes tighten the LP relaxations that guide heuristic search.
• Supply-chain and logistics: vehicle routing, warehouse picking, and container loading are IP problems where cutting-plane-enhanced branch and bound finds provably near-optimal solutions.
• Network design and telecommunications: choosing which links to build in a fiber network, or which base stations to activate, are classic IP problems solved daily with MIP solvers.
• Proof complexity and cryptography: cutting-plane proof systems (Chvátal-Gomory proofs) are studied as a model of mathematical reasoning; their limitations inform the design of cryptographic hardness assumptions.

Learn how cutting planes work and you understand integer programming, branch and bound, and why the world's hardest scheduling problems can still be solved on a laptop.

Cutting planes embody one of the most elegant ideas in optimization: if the easy continuous problem gives you a fractional answer you can't use, add a law that forbids that fraction without banning any integer solution you actually want. Repeat until reality is forced to be discrete.

Gomory's 1958 theorem guarantees this process terminates. The exponential worst case reminds us that integer programming is genuinely hard — NP-hard, sitting right next to P vs NP. Yet in practice, a few rounds of cuts plus branch and bound routinely tame problems with millions of variables, scheduling the flights you board and routing the parcels at your door.

The next time an airline reshuffles its crew list overnight or a logistics company finds a near-perfect delivery route before dawn, a cutting-plane algorithm is almost certainly behind it.