Introduction

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.

Try It: Tighten the LP Step by Step

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">Integer program: maximize <b>x + y</b> subject to <b>2x + y ≤ 7</b> and <b>x + 2y ≤ 7</b>, x, y ≥ 0 integer. The LP relaxation optimum is fractional. Press <b>Add Gomory Cut</b> to slice it off.</p>
<canvas id="cv" width="320" height="300"></canvas>
<div class="info" id="info"></div>
<div class="btns">
  <button id="cut" type="button">Add Gomory Cut</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Integer program: max x+y  s.t.  2x+y<=7,  x+2y<=7,  x,y>=0 integer
// LP relaxation optimum: 2x+y=7 & x+2y=7 => subtract: x-y=0 => x=y
//   3x=7 => x=y=7/3 ≈ 2.333, obj = 14/3 ≈ 4.667 (FRACTIONAL)
// True integer optimum: obj=4 at (3,1),(2,2),(1,3)
//
// Gomory cuts (both valid for all 13 feasible integer points):
//   Cut 1: 2x+2y<=9  (from 3x+3y<=14 => round half: 2x+2y<=9)
//          At LP opt: 2*7/3+2*7/3=28/3≈9.33 > 9 → cuts it off ✓
//          Max 2x+2y over integers = 2*4=8 ≤ 9 → valid ✓
//   Cut 2: x+y<=4    (from 3x+3y<=14 => floor: x+y<=4)
//          At LP opt after cut 1: (2.5, 2.0) → 2.5+2.0=4.5 > 4 → cuts it off ✓
//          Max x+y over integers = 4 ≤ 4 → valid ✓
//   After cut 2: LP opt = (3,1) which is INTEGER ✓

const CW = 320, CH = 300;
const PAD = 44, XMAX = 5, YMAX = 5;
const EPS = 1e-9;

function toPixel(x, y) {
  return [PAD + (x / XMAX) * (CW - PAD - 12),
          CH - PAD - (y / YMAX) * (CH - PAD - 12)];
}

const BASE_CONS = [
  [2, 1, 7, '2x+y=7'],
  [1, 2, 7, 'x+2y=7'],
  [1, 0, XMAX, ''],
  [0, 1, YMAX, ''],
  [-1, 0, 0, ''],
  [0, -1, 0, '']
];

const GOMORY_CUTS = [
  [2, 2, 9, '2x+2y ≤ 9', 'Cut 1'],
  [1, 1, 4, 'x+y ≤ 4',   'Cut 2']
];

const CUT_COLORS = ['#e63946', '#9b59b6'];
let cuts = [];

function lpOpt(cons) {
  let best = null, bestV = -Infinity;
  for (let i = 0; i < cons.length; i++) {
    for (let j = i + 1; j < cons.length; j++) {
      const [a1,b1,c1] = cons[i], [a2,b2,c2] = cons[j];
      const det = a1*b2 - a2*b1;
      if (Math.abs(det) < EPS) continue;
      const x = (c1*b2 - c2*b1) / det;
      const y = (a1*c2 - a2*c1) / det;
      if (x < -EPS || y < -EPS) continue;
      if (cons.every(([a,b,c]) => a*x + b*y <= c + EPS)) {
        const v = x + y;
        if (v > bestV + EPS) { bestV = v; best = [x, y]; }
      }
    }
  }
  return best;
}

function polytope(cons) {
  const pts = [];
  for (let i = 0; i < cons.length; i++) {
    for (let j = i + 1; j < cons.length; j++) {
      const [a1,b1,c1] = cons[i], [a2,b2,c2] = cons[j];
      const det = a1*b2 - a2*b1;
      if (Math.abs(det) < EPS) continue;
      const x = (c1*b2 - c2*b1) / det;
      const y = (a1*c2 - a2*c1) / det;
      if (x < -EPS || y < -EPS) continue;
      if (cons.every(([a,b,c]) => a*x + b*y <= c + EPS))
        pts.push([x, y]);
    }
  }
  if (!pts.length) return [];
  const cx = pts.reduce((s,p) => s+p[0], 0) / pts.length;
  const cy = pts.reduce((s,p) => s+p[1], 0) / pts.length;
  pts.sort((a,b) => Math.atan2(a[1]-cy,a[0]-cx) - Math.atan2(b[1]-cy,b[0]-cx));
  return pts;
}

function draw() {
  const cv = document.getElementById('cv');
  const ctx = cv.getContext('2d');
  ctx.clearRect(0, 0, CW, CH);

  const cons = [...BASE_CONS, ...cuts];
  const poly = polytope(cons);

  // Shade feasible region
  if (poly.length > 1) {
    ctx.beginPath();
    const [px0, py0] = toPixel(...poly[0]);
    ctx.moveTo(px0, py0);
    for (let i = 1; i < poly.length; i++) {
      const [px, py] = toPixel(...poly[i]);
      ctx.lineTo(px, py);
    }
    ctx.closePath();
    ctx.fillStyle = 'rgba(29,53,87,0.13)';
    ctx.fill();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 1.8;
    ctx.stroke();
  }

  // Grid lines (dashed)
  ctx.strokeStyle = '#ddd'; ctx.lineWidth = 1; ctx.setLineDash([2,3]);
  for (let v = 1; v <= XMAX; v++) {
    const [px,,] = toPixel(v, 0); const [,py0] = toPixel(0, 0); const [,py1] = toPixel(0, YMAX);
    ctx.beginPath(); ctx.moveTo(px, py0); ctx.lineTo(px, py1); ctx.stroke();
  }
  for (let v = 1; v <= YMAX; v++) {
    const [,py] = toPixel(0, v); const [px0] = toPixel(0, 0); const [px1] = toPixel(XMAX, 0);
    ctx.beginPath(); ctx.moveTo(px0, py); ctx.lineTo(px1, py); ctx.stroke();
  }
  ctx.setLineDash([]);

  // Axes
  ctx.strokeStyle = '#aaa'; ctx.lineWidth = 1.2;
  const [ax0,ay0]=toPixel(0,0); const [ax1]=toPixel(XMAX,0); const [,ay1]=toPixel(0,YMAX);
  ctx.beginPath(); ctx.moveTo(ax0,ay0); ctx.lineTo(ax1,ay0); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(ax0,ay0); ctx.lineTo(ax0,ay1); ctx.stroke();

  // Axis labels
  ctx.fillStyle = '#888'; ctx.font = '11px system-ui'; ctx.textAlign = 'center';
  for (let v = 0; v <= XMAX; v++) {
    const [px, py] = toPixel(v, 0); ctx.fillText(v, px, py + 14);
  }
  ctx.textAlign = 'right';
  for (let v = 1; v <= YMAX; v++) {
    const [px, py] = toPixel(0, v); ctx.fillText(v, px - 4, py + 4);
  }
  ctx.fillStyle = '#555'; ctx.font = '12px system-ui'; ctx.textAlign = 'left';
  ctx.fillText('x', toPixel(XMAX,0)[0]-2, toPixel(XMAX,0)[1]+14);
  ctx.fillText('y', toPixel(0,YMAX)[0]-14, toPixel(0,YMAX)[1]+4);

  // Integer lattice points
  for (let xi = 0; xi <= XMAX; xi++) {
    for (let yi = 0; yi <= YMAX; yi++) {
      if (!BASE_CONS.every(([a,b,c]) => a*xi+b*yi <= c+EPS)) continue;
      const [px, py] = toPixel(xi, yi);
      const inCurrent = cons.every(([a,b,c]) => a*xi+b*yi <= c+EPS);
      ctx.beginPath();
      ctx.arc(px, py, 4, 0, 2*Math.PI);
      ctx.fillStyle = inCurrent ? '#0a7d33' : '#ddd';
      ctx.fill();
      if (inCurrent) {
        ctx.strokeStyle = '#085e27'; ctx.lineWidth = 1;
        ctx.stroke();
      }
    }
  }

  // Draw constraint boundary lines (original)
  const lineConf = [
    { cons: BASE_CONS[0], color: '#1d3557', dash: [] },
    { cons: BASE_CONS[1], color: '#1d3557', dash: [] }
  ];
  lineConf.forEach(({cons: c, color, dash}) => {
    const [a,b,cc] = c;
    const pts2 = [];
    if (Math.abs(b) > EPS) {
      for (let xi = 0; xi <= XMAX+0.1; xi += 0.05) {
        const yi = (cc - a*xi) / b;
        if (yi >= -0.1 && yi <= YMAX+0.2) pts2.push([xi, yi]);
      }
    }
    if (pts2.length < 2) return;
    ctx.strokeStyle = color; ctx.lineWidth = 1.5; ctx.setLineDash(dash);
    ctx.beginPath();
    const [p0x,p0y]=toPixel(...pts2[0]); ctx.moveTo(p0x,p0y);
    pts2.slice(1).forEach(p => { const [px,py]=toPixel(...p); ctx.lineTo(px,py); });
    ctx.stroke(); ctx.setLineDash([]);
  });
  // Label constraints
  ctx.font = '11px system-ui'; ctx.fillStyle = '#1d3557'; ctx.textAlign = 'left';
  ctx.fillText('2x+y=7', toPixel(0.1, 6.9)[0], toPixel(0.1, 6.9)[1]);
  ctx.fillText('x+2y=7', toPixel(3.3, 1.85)[0]-2, toPixel(3.3, 1.85)[1]-8);

  // Gomory cut lines
  cuts.forEach(([a, b, c, label, cutName], idx) => {
    const color = CUT_COLORS[idx % CUT_COLORS.length];
    ctx.strokeStyle = color; ctx.lineWidth = 2; ctx.setLineDash([6, 3]);
    const pts2 = [];
    if (Math.abs(b) > EPS) {
      for (let xi = 0; xi <= XMAX+0.2; xi += 0.02) {
        const yi = (c - a*xi) / b;
        if (yi >= -0.15 && yi <= YMAX+0.2) pts2.push([xi, yi]);
      }
    } else if (Math.abs(a) > EPS) {
      pts2.push([c/a, 0], [c/a, YMAX]);
    }
    if (pts2.length > 1) {
      ctx.beginPath();
      const [p0x,p0y]=toPixel(...pts2[0]); ctx.moveTo(p0x,p0y);
      pts2.slice(1).forEach(p=>{ const [px,py]=toPixel(...p); ctx.lineTo(px,py); });
      ctx.stroke();
    }
    ctx.setLineDash([]);
    // Cut label
    ctx.fillStyle = color; ctx.font = 'bold 11px system-ui'; ctx.textAlign = 'left';
    let lx = 0.15, ly;
    if (Math.abs(b) > EPS) ly = Math.min((c - a*0.15)/b - 0.35, YMAX - 0.4);
    else { lx = c/a + 0.12; ly = YMAX * 0.6; }
    if (ly < 0.1) { lx = (c - b*0.1)/a + 0.1; ly = 0.1; }
    const [lpx,lpy]=toPixel(Math.min(lx,XMAX-0.5), Math.max(0.05,Math.min(ly,YMAX-0.2)));
    ctx.fillText(cutName + ': ' + label, lpx, lpy);
  });

  // LP optimum star
  const opt = lpOpt(cons);
  if (opt) {
    const [ox, oy] = opt;
    const [px, py] = toPixel(ox, oy);
    const isInt = Math.abs(ox-Math.round(ox)) < 0.002 && Math.abs(oy-Math.round(oy)) < 0.002;
    ctx.font = 'bold 20px system-ui'; ctx.textAlign = 'center';
    ctx.fillStyle = isInt ? '#0a7d33' : '#e63946';
    ctx.fillText('★', px, py+7);
    ctx.font = '10px system-ui';
    ctx.fillStyle = '#222';
    ctx.fillText('(' + ox.toFixed(2) + ', ' + oy.toFixed(2) + ')  obj=' + (ox+oy).toFixed(2), px, py - 10);
  }
}

function setInfo(html) { document.getElementById('info').innerHTML = html; }

function addCut() {
  if (cuts.length >= GOMORY_CUTS.length) {
    setInfo('<span class="ok">✓ Already at the integer optimum — no more cuts needed.</span>');
    return;
  }
  const c = GOMORY_CUTS[cuts.length];
  cuts.push(c);
  draw();
  const cons = [...BASE_CONS, ...cuts];
  const opt = lpOpt(cons);
  if (opt) {
    const [ox, oy] = opt;
    const isInt = Math.abs(ox-Math.round(ox)) < 0.002 && Math.abs(oy-Math.round(oy)) < 0.002;
    const cutStr = fmt('<span class="cut">Added: <b>%v%: %v2%</b></span>', { v: c[4], v2: c[3] });
    if (isInt) {
      const xi = Math.round(ox), yi = Math.round(oy);
      setInfo(fmt('%cutStr%<br><span class="ok">✓ LP optimum is now integer: (%xi%, %yi%), obj = %xi%%yi%</span>', { cutStr: cutStr, xi: xi, yi: yi }));
      document.getElementById('cut').disabled = true;
    } else {
      setInfo(fmt('%cutStr%<br>LP optimum still fractional: (%ox%, %oy%)  obj=%v% — add another cut.', { cutStr: cutStr, ox: ox.toFixed(3), oy: oy.toFixed(3), v: (ox+oy).toFixed(3) }));
    }
    console.log('Cut:', c[3], '| LP opt:', ox.toFixed(4), oy.toFixed(4), 'obj:', (ox+oy).toFixed(4), 'integer?', isInt);
  }
}

function reset() {
  cuts = [];
  document.getElementById('cut').disabled = false;
  const opt = lpOpt(BASE_CONS);
  setInfo(fmt('LP relaxation optimum: <b>(%v%, %v2%)</b>  obj=%v3% — <b>fractional</b>. Press <b>Add Gomory Cut</b>.', { v: opt[0].toFixed(3), v2: opt[1].toFixed(3), v3: (opt[0]+opt[1]).toFixed(3) }));
  draw();
  console.log('Reset. Initial LP opt:', opt[0].toFixed(6), opt[1].toFixed(6), 'obj:', (opt[0]+opt[1]).toFixed(6));
}

document.getElementById('cut').addEventListener('click', addCut);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/cutting-planes/Content licensed under CC BY-NC 4.0.