Introduction

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.

Try It

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">Search Tree</div>
    <svg id="tree-svg" width="380" height="180"></svg>
  </div>
  <div id="log"></div>
  <div class="btns">
    <button id="btn-step">Step</button>
    <button id="btn-solve">Solve All</button>
    <button id="btn-reset" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Branch-and-Cut demo
// Problem: maximize 5x + 4y
//   s.t. 6x + 4y <= 24
//        x + 2y <= 6
//        x, y >= 0, integer
//
// LP optimum (ignoring integrality): x=3, y=1.5 => obj=5*3+4*1.5=15+6=21
// Integer optimum: x=4, y=0 => obj=20  (verified by enumeration)
// A Gomory cut from y fractional: y <= floor(1.5) = 1.
// After adding cut y<=1: LP optimum is x=10/3, y=1 => obj=50/3+4=20.67
//   x=10/3 fractional => branch x<=3 and x>=4
//   x>=4: 6*4+4y<=24 => y<=0; x+2y<=6 => y<=1 => y=0; obj=20 (integer!)
//   x<=3: obj = 5*3+4*1=19 (integer)
//   best = max(20, 19) = 20  wait — let's verify: x=4,y=0: 6*4=24<=24 ok; 4+0=4<=6 ok; obj=20
//   Actually optimal is x=4,y=0 with obj=20.
// Let’s enumerate all integer points to verify:
//   x=0: 4y<=24 => y<=6; 2y<=6 => y<=3. Best: y=3 obj=12
//   x=1: 4y<=18 => y<=4; 2y<=4 => y<=2. Best: y=2 obj=13
//   x=2: 4y<=12 => y<=3; 2y<=2 => y<=1. Best: y=1 obj=14
//   x=3: 4y<=6 => y<=1; 2y<=0 => y<=0. Wait: x=3: 6*3=18, 4y<=6 => y<=1.5 => y<=1;
//         x+2y<=6 => 2y<=3 => y<=1. Best y=1 obj=19
//   x=4: 6*4=24<=24 ok; x+2y<=6 => 2y<=2 => y<=1; 4*4=16+4y<=24 => 4y<=8 => y<=2; min => y<=1
//         but also y>=0. obj max = 5*4+4*1=24; check: 6*4+4*1=28 > 24 VIOLATES c1!
//         so y=0: 6*4+0=24<=24 ok; 4+0=4<=6 ok. obj=20
//         y=1: 6*4+4=28>24 INFEASIBLE
//   x=4,y=0: obj=20. OPTIMAL.
//
// Steps for demo:
// Node 0 (root): LP relax => x=3, y=1.5, obj=22.5
// Apply Gomory cut y<=1 => node 0 updated LP: x=10/3, y=1, obj=21.67
// Branch on x (fractional 10/3≈3.33): x<=3 and x>=4
// Node 1 (x<=3): LP => x=3,y=1, obj=19. INTEGER => incumbent=19
// Node 2 (x>=4): LP => x=4,y=0, obj=20. INTEGER => 20>19 => new incumbent=20
// Done. Optimal x=4,y=0,obj=20.

const STEPS = [
  {
    phase:`LP Relaxation (Root)`,
    point:{x:3, y:1.5},
    obj:21,
    cuts:[],
    branches:[],
    note:`LP relaxation: ignore integrality. Optimum x=3, y=1.5, obj=21. Variable y is fractional — not integer.`,
    treeNodes:[{id:0,label:`Root
LP=21
x=3, y=1.5`,x:190,y:30,state:'active'}],
    treeEdges:[]
  },
  {
    phase:`Add Gomory Cut: y ≤ 1`,
    point:{x:10/3, y:1},
    obj:21,
    cuts:[{a:0,b:1,c:1}], // y <= 1
    branches:[],
    note:`Gomory cut from y fractional: add y ≤ 1. New LP optimum: x=10/3≈3.33, y=1, obj≈20.67. Now x is fractional.`,
    treeNodes:[{id:0,label:`Root
LP=20.67
x=3.33, y=1`,x:190,y:30,state:'cut'}],
    treeEdges:[]
  },
  {
    phase:`Branch on x: x ≤ 3 or x ≥ 4`,
    point:{x:10/3, y:1},
    obj:20.67,
    cuts:[{a:0,b:1,c:1}],
    branches:[{type:'le',val:3},{type:'ge',val:4}],
    note:`x≈3.33 is fractional. Branch: left subproblem x≤3, right subproblem x≥4.`,
    treeNodes:[
      {id:0,label:`Root
LP=20.67`,x:190,y:30,state:'branched'},
      {id:1,label:`x ≤ 3
(open)`,x:90,y:120,state:'open'},
      {id:2,label:`x ≥ 4
(open)`,x:290,y:120,state:'open'}
    ],
    treeEdges:[{from:0,to:1,label:'x≤3'},{from:0,to:2,label:'x≥4'}]
  },
  {
    phase:`Solve left node: x ≤ 3`,
    point:{x:3, y:1},
    obj:19,
    cuts:[{a:0,b:1,c:1}],
    branches:[{type:'le',val:3}],
    note:`Node x≤3: LP gives x=3, y=1, obj=19. Both integer! Incumbent = 19.`,
    treeNodes:[
      {id:0,label:`Root
LP=20.67`,x:190,y:30,state:'branched'},
      {id:1,label:`x ≤ 3
obj=19 ✓
INCUMBENT`,x:90,y:120,state:'integer'},
      {id:2,label:`x ≥ 4
(open)`,x:290,y:120,state:'open'}
    ],
    treeEdges:[{from:0,to:1,label:'x≤3'},{from:0,to:2,label:'x≥4'}]
  },
  {
    phase:`Solve right node: x ≥ 4`,
    point:{x:4, y:0},
    obj:20,
    cuts:[{a:0,b:1,c:1}],
    branches:[{type:'ge',val:4}],
    note:`Node x≥4: LP gives x=4, y=0, obj=20. Both integer! 20 > 19 → new incumbent = 20.`,
    treeNodes:[
      {id:0,label:`Root
LP=20.67`,x:190,y:30,state:'branched'},
      {id:1,label:`x ≤ 3
obj=19`,x:90,y:120,state:'pruned'},
      {id:2,label:`x ≥ 4
obj=20 ✓
OPTIMAL`,x:290,y:120,state:'integer'}
    ],
    treeEdges:[{from:0,to:1,label:'x≤3'},{from:0,to:2,label:'x≥4'}]
  },
  {
    phase:`DONE — Optimal Solution Found`,
    point:{x:4, y:0},
    obj:20,
    cuts:[{a:0,b:1,c:1}],
    branches:[{type:'ge',val:4}],
    note:`All nodes explored or pruned. OPTIMAL: x=4, y=0, objective = 20.`,
    treeNodes:[
      {id:0,label:`Root
LP=20.67`,x:190,y:30,state:'branched'},
      {id:1,label:`x ≤ 3
obj=19`,x:90,y:120,state:'pruned'},
      {id:2,label:`x ≥ 4
obj=20 ✓
OPTIMAL`,x:290,y:120,state:'optimal'}
    ],
    treeEdges:[{from:0,to:1,label:'x≤3'},{from:0,to:2,label:'x≥4'}]
  }
];

// Canvas drawing
const cvs = document.getElementById('cvs');
const ctx = cvs.getContext('2d');
const SCALE = 40; // pixels per unit
const OX = 30, OY = 280; // origin in canvas coords

function toCanvas(x, y) { return [OX + x*SCALE, OY - y*SCALE]; }

function drawScene(stepIdx) {
  const s = STEPS[stepIdx];
  ctx.clearRect(0, 0, cvs.width, cvs.height);

  // Grid
  ctx.strokeStyle = '#e0e8f0'; ctx.lineWidth = 0.5;
  for (let i = 0; i <= 7; i++) {
    const [x0,y0] = toCanvas(i,0), [x1,y1] = toCanvas(i,7);
    ctx.beginPath(); ctx.moveTo(x0,y0); ctx.lineTo(x1,y1); ctx.stroke();
    const [xa,ya] = toCanvas(0,i), [xb,yb] = toCanvas(7,i);
    ctx.beginPath(); ctx.moveTo(xa,ya); ctx.lineTo(xb,yb); ctx.stroke();
  }

  // Axes
  ctx.strokeStyle = '#457b9d'; ctx.lineWidth = 1.5;
  const [ax0,ay0] = toCanvas(0,0), [ax1,ay1] = toCanvas(7,0);
  ctx.beginPath(); ctx.moveTo(ax0,ay0); ctx.lineTo(ax1,ay1); ctx.stroke();
  const [bx0,by0] = toCanvas(0,0), [bx1,by1] = toCanvas(0,7);
  ctx.beginPath(); ctx.moveTo(bx0,by0); ctx.lineTo(bx1,by1); ctx.stroke();

  // Axis labels
  ctx.fillStyle = '#457b9d'; ctx.font = '11px system-ui'; ctx.textAlign = 'center';
  for (let i = 1; i <= 6; i++) {
    const [cx,cy] = toCanvas(i, 0); ctx.fillText(i, cx, cy+14);
    const [dx,dy] = toCanvas(0, i); ctx.textAlign='right'; ctx.fillText(i, dx-4, dy+4); ctx.textAlign='center';
  }
  ctx.fillStyle = '#1d3557'; ctx.font = 'bold 11px system-ui';
  const [lx,ly] = toCanvas(7,0); ctx.fillText('x', lx+4, ly+4);
  const [ly2x, ly2y] = toCanvas(0,7); ctx.fillText('y', ly2x-4, ly2y-4);

  // Feasible region (LP: 6x+4y<=24, x+2y<=6, x>=0, y>=0)
  // Vertices of LP feasible region: (0,0),(4,0),(3,1.5),(0,3)
  ctx.fillStyle = 'rgba(173, 216, 230, 0.35)';
  ctx.beginPath();
  const verts = [[0,0],[4,0],[3,1.5],[0,3]];
  verts.forEach(([vx,vy], i) => {
    const [cx,cy] = toCanvas(vx,vy);
    i===0 ? ctx.moveTo(cx,cy) : ctx.lineTo(cx,cy);
  });
  ctx.closePath(); ctx.fill();

  // Constraint lines
  // 6x+4y=24 => y=(24-6x)/4
  ctx.strokeStyle = '#1d6fa0'; ctx.lineWidth = 1.5; ctx.setLineDash([5,3]);
  ctx.beginPath();
  ctx.moveTo(...toCanvas(0,6)); ctx.lineTo(...toCanvas(4,0));
  ctx.stroke();
  ctx.beginPath();
  // x+2y=6 => y=(6-x)/2
  ctx.moveTo(...toCanvas(0,3)); ctx.lineTo(...toCanvas(6,0));
  ctx.stroke();
  ctx.setLineDash([]);

  // Gomory cut: y <= 1 (horizontal line y=1)
  if (s.cuts.length > 0) {
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2; ctx.setLineDash([4,2]);
    ctx.beginPath();
    ctx.moveTo(...toCanvas(0,1)); ctx.lineTo(...toCanvas(5,1));
    ctx.stroke();
    ctx.setLineDash([]);
    ctx.fillStyle = '#e63946'; ctx.font = '11px system-ui'; ctx.textAlign = 'left';
    const [gx,gy] = toCanvas(4.1,1.05); ctx.fillText(`cut: y≤1`, gx, gy);
  }

  // Branch constraints
  if (s.branches.length > 0) {
    s.branches.forEach(b => {
      ctx.strokeStyle = '#f4a261'; ctx.lineWidth = 2; ctx.setLineDash([3,3]);
      const xv = b.val;
      ctx.beginPath();
      ctx.moveTo(...toCanvas(xv,0)); ctx.lineTo(...toCanvas(xv,3.5));
      ctx.stroke();
      ctx.setLineDash([]);
      ctx.fillStyle = '#f4a261'; ctx.font = '11px system-ui'; ctx.textAlign = 'center';
      const [bx,by] = toCanvas(xv, 3.7);
      ctx.fillText('x'+(b.type==='le'?'≤':'≥')+b.val, bx, by);
    });
  }

  // Integer points
  ctx.fillStyle = '#1d3557';
  for (let xi = 0; xi <= 4; xi++) {
    for (let yi = 0; yi <= 4; yi++) {
      if (6*xi+4*yi <= 24 && xi+2*yi <= 6) {
        const [px,py] = toCanvas(xi,yi);
        ctx.beginPath(); ctx.arc(px,py,3,0,Math.PI*2); ctx.fill();
      }
    }
  }

  // LP optimum point
  const [px, py] = toCanvas(s.point.x, s.point.y);
  const isInt = Number.isInteger(s.point.x) && Number.isInteger(s.point.y);
  ctx.fillStyle = isInt ? '#0a7d33' : '#e63946';
  ctx.strokeStyle = '#fff'; ctx.lineWidth = 2;
  ctx.beginPath(); ctx.arc(px, py, 7, 0, Math.PI*2);
  ctx.fill(); ctx.stroke();
  ctx.fillStyle = '#1d3557'; ctx.font = 'bold 11px system-ui'; ctx.textAlign = 'left';
  ctx.fillText('('+(Math.round(s.point.x*100)/100)+','+(Math.round(s.point.y*100)/100)+')', px+10, py-5);
  ctx.fillText('obj='+Math.round(s.obj*100)/100, px+10, py+10);
}

// Tree drawing
function drawTree(stepIdx) {
  const s = STEPS[stepIdx];
  const svg = document.getElementById('tree-svg');
  svg.innerHTML = '';
  const ns = 'http://www.w3.org/2000/svg';
  const nodeColors = {active:'#457b9d', cut:'#a23b72', branched:'#f4a261',
    open:'#cdd9e3', integer:'#0a7d33', pruned:'#aaa', optimal:'#1d6fa0'};
  const textColors = {active:'#fff', cut:'#fff', branched:'#fff',
    open:'#1d3557', integer:'#fff', pruned:'#555', optimal:'#fff'};

  // Edges first
  s.treeEdges.forEach(e => {
    const from = s.treeNodes.find(n=>n.id===e.from);
    const to = s.treeNodes.find(n=>n.id===e.to);
    const line = document.createElementNS(ns,'line');
    line.setAttribute('x1', from.x); line.setAttribute('y1', from.y+20);
    line.setAttribute('x2', to.x); line.setAttribute('y2', to.y-20);
    line.setAttribute('stroke', '#aaa'); line.setAttribute('stroke-width', '1.5');
    svg.appendChild(line);
    const mid = [(from.x+to.x)/2, (from.y+to.y)/2+5];
    const txt = document.createElementNS(ns,'text');
    txt.setAttribute('x', mid[0]); txt.setAttribute('y', mid[1]);
    txt.setAttribute('text-anchor','middle'); txt.setAttribute('font-size','10');
    txt.setAttribute('fill','#888'); txt.textContent = e.label;
    svg.appendChild(txt);
  });

  // Nodes
  s.treeNodes.forEach(n => {
    const g = document.createElementNS(ns,'g');
    const rx = 52, ry = 18;
    const rect = document.createElementNS(ns,'rect');
    rect.setAttribute('x', n.x-rx); rect.setAttribute('y', n.y-ry);
    rect.setAttribute('width', rx*2); rect.setAttribute('height', ry*2);
    rect.setAttribute('rx', 8);
    rect.setAttribute('fill', nodeColors[n.state]||'#cdd9e3');
    rect.setAttribute('stroke', '#1d3557'); rect.setAttribute('stroke-width','1');
    g.appendChild(rect);

    const lines = n.label.split('\n');
    lines.forEach((line, i) => {
      const t = document.createElementNS(ns,'text');
      const yOff = (i - (lines.length-1)/2) * 13;
      t.setAttribute('x', n.x); t.setAttribute('y', n.y + yOff + 4);
      t.setAttribute('text-anchor','middle'); t.setAttribute('font-size','10');
      t.setAttribute('font-weight', i===0?'bold':'normal');
      t.setAttribute('fill', textColors[n.state]||'#1d3557');
      t.textContent = line;
      g.appendChild(t);
    });
    svg.appendChild(g);
  });
}

let currentStep = 0;
const totalSteps = STEPS.length;

function updateLog(idx) {
  document.getElementById('log').textContent = fmt(`Step %idx%%v%/%totalSteps%: %phase% — %note%`, { idx: idx, v: 1, totalSteps: totalSteps, phase: STEPS[idx].phase, note: STEPS[idx].note });
}

function render(idx) {
  drawScene(idx);
  drawTree(idx);
  updateLog(idx);
  document.getElementById('btn-step').disabled = idx >= totalSteps-1;
}

document.getElementById('btn-step').addEventListener('click', () => {
  if (currentStep < totalSteps-1) { currentStep++; render(currentStep); }
});
document.getElementById('btn-solve').addEventListener('click', () => {
  currentStep = totalSteps-1; render(currentStep);
});
document.getElementById('btn-reset').addEventListener('click', () => {
  currentStep = 0; render(0);
});

render(0);
Result
Console

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.

The Real Complexity

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 xix_{i} = f and creates two subproblems: one with xix_{i} ≤ ⌊f⌋ and one with xix_{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/branch-and-cut/Content licensed under CC BY-NC 4.0.