Branch-and-Cut

Every day, airlines decide which crews fly which routes, chip designers pack millions of transistors onto silicon, and logistics companies route thousands of delivery trucks. All of these are integer programs: optimization problems where the decision variables must be whole numbers — you can't assign 0.7 of a crew member.

Integer programming is NP-hard in general. Brute-force enumeration over all possible assignments is hopeless for any realistically sized problem. Yet commercial solvers like CPLEX, Gurobi, and SCIP routinely crack problems with millions of variables in minutes. Their secret is branch-and-cut.

Branch-and-cut is not an approximation. It finds the provably optimal integer solution, or proves none exists. It does this by interleaving two classical ideas — a search tree that splits on fractional variables, and cutting planes that slice away fractional space without removing any integer point. Together, they shrink the search so aggressively that the exponential worst case rarely bites in practice.

The demo below solves the integer program maximize 5x + 4y subject to 6x + 4y ≤ 24, x + 2y ≤ 6, and x, y ≥ 0 integers. Press Step to advance one node at a time, or Solve to run the full algorithm. Watch how the LP relaxation gives the fractional optimum x=3, y=1.5, obj=21, a Gomory cut tightens the feasible region, and branching on the remaining fractional variable eventually proves the integer optimum is x=4, y=0, obj=20.

<div class="bnc-wrap">
  <div class="problem-box">
    <b>{{maximize}}</b> 5x + 4y<br>
    {{subject_to}}: 6x + 4y &le; 24 &nbsp;|&nbsp; x + 2y &le; 6 &nbsp;|&nbsp; x, y &ge; 0, <b>integer</b>
  </div>
  <div class="canvas-wrap">
    <canvas id="cvs" width="300" height="300"></canvas>
  </div>
  <div id="tree-wrap">
    <div class="tree-label">{{tree_label}}</div>
    <svg id="tree-svg" width="380" height="180"></svg>
  </div>
  <div id="log"></div>
  <div class="btns">
    <button id="btn-step">{{btn_step}}</button>
    <button id="btn-solve">{{btn_solve}}</button>
    <button id="btn-reset" class="ghost">{{btn_reset}}</button>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1d3557; }
.bnc-wrap { display: flex; flex-direction: column; gap: .6rem; }
.problem-box { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px;
  padding: .5rem .8rem; font-size: .88rem; line-height: 1.6; }
.canvas-wrap { display: flex; justify-content: center; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc; display: block; }
#tree-wrap { background: #f8fafc; border: 1px solid #cdd9e3; border-radius: 8px; padding: .4rem .6rem; }
.tree-label { font-size: .78rem; font-weight: 700; color: #457b9d; margin-bottom: .2rem; }
#log { font-size: .82rem; line-height: 1.5; min-height: 2.4em; color: #1d3557;
  background: #f0f4f8; border-radius: 6px; padding: .35rem .6rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
  background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice the asymmetry: checking whether a candidate integer solution satisfies all constraints is instant. Finding the best one — and proving it is best — requires exploring (and pruning) an exponential tree. Branch-and-cut achieves this by combining two bounds: the LP upper bound and the best integer solution found so far (the incumbent). Any node whose LP bound cannot beat the incumbent is pruned immediately.

Integer Linear Programming (ILP) is NP-hard. This is a proven fact: any problem in NP can be encoded as an ILP, so a polynomial-time ILP solver would imply P = NP. In the worst case, branch-and-cut explores an exponential number of nodes.

What makes it powerful in practice is the LP relaxation: drop the integrality constraint and solve with the simplex method in polynomial time. The LP optimum is always ≥ the ILP optimum (it has more freedom), giving an upper bound. If the LP solution happens to be integer, we're done. If not:

• Cutting planes are inequalities that are valid for all integer feasible points but cut off the current fractional LP solution. Adding them tightens the relaxation without removing any integer solution. The classic example is Gomory cuts (Ralph Gomory, 1958), derived mechanically from any LP tableau row where a basic variable is fractional.
• Branching picks a fractional variable $x_{i}$ = f and creates two subproblems: one with $x_{i}$ ≤ ⌊f⌋ and one with $x_{i}$ ≥ ⌈f⌉. This splits the search space.
• Pruning: if a node's LP bound ≤ incumbent, or the LP is infeasible, the entire subtree is discarded.

The modern framework (Padberg & Rinaldi, 1991 for TSP; generalized through the 1990s) adds problem-specific cuts — subtour elimination for TSP, knapsack covers, clique inequalities — that can make the LP bound extremely tight, often within 1% of integer optimum before any branching. Such strong bounds mean the tree stays small enough to solve in practice, even for NP-hard instances.

The theoretical worst case remains exponential, and for random instances without structure it can be. But for the structured problems of industry, the tree is typically polynomial in size.

Branch-and-cut is the engine behind a remarkable range of high-stakes decisions:

• Airline scheduling: crew and aircraft assignment is a giant set-covering ILP with millions of variables. Airlines save hundreds of millions of dollars annually through optimal or near-optimal solutions produced by branch-and-cut solvers.
• VLSI / chip design: placing circuit blocks and routing wires is an ILP. Modern CPUs would be impossible to design without automated integer programming.
• Logistics and routing: vehicle routing, warehouse slotting, and network design are all modeled as ILPs. The Traveling Salesman Problem — the canonical NP-hard routing problem — was first solved to world-record sizes using branch-and-cut (Padberg & Rinaldi, 1991).
• Energy grids: unit commitment (which power plants to turn on and when) is an ILP solved daily by every major grid operator.
• Healthcare and sports: nurse scheduling, operating room assignment, tournament bracket design — all solved as integer programs.

The common thread: any "yes/no" or "which one" decision that must optimize a linear objective is an ILP candidate. If you can write it down as one, branch-and-cut will likely find the exact optimum faster than you'd expect.

Branch-and-cut is one of the great practical victories over NP-hardness. Theory says integer programming is exponentially hard. Practice says branch-and-cut solves million-variable airline scheduling problems before the flight departs.

The key insight is geometric: the LP relaxation gives a cheap upper bound, cutting planes tighten that bound toward the integer hull, and branching handles whatever fractional variables survive the cuts. The three ideas reinforce each other: tighter cuts mean fewer branches; fewer branches mean less time. On structured industrial instances, the tree stays astonishingly small.

So the next time you board a perfectly scheduled flight or carry a microchip with billions of transistors, remember: the allocation underneath was almost certainly found by branch-and-cut, an algorithm that makes the NP-hard surrender — not in theory, but in the time it takes to make a cup of coffee.