Introduction

A factory plans next week: how many of each product to build to maximize profit, within limits on labor, materials and machines. A transit agency decides how many buses to run on each route. A bank picks which projects to fund. All of these are the same shape: maximize (or minimize) a goal, subject to constraints — and the decisions must be whole numbers. You can't build half a product or run 2.6 buses.

That master form is integer programming. Drop the whole-number requirement and you get linear programming (LP) — and LP is easy, solvable in polynomial time. The catch is precisely the integers: the moment you insist on whole numbers, the problem becomes NP-hard.

This article is a hub. Knapsack, graph coloring, set cover, scheduling — many problems on this site can be written as integer programs. So understanding why integers make optimization hard explains a huge swath of the hard-problem landscape at once.

LP vs Integer

Try it. Here's a tiny problem: maximize x + y inside a shaded region. The LP optimum (ignoring whole numbers) sits at a corner — but its coordinates are fractional. The integer optimum must land on a grid point inside the region.

<p class="hint">Maximize <b>x + y</b> inside the shaded region (constraints −x+y ≤ 1 and
    8x+2y ≤ 19, with x,y ≥ 0). The LP optimum ignores whole numbers; the integer optimum must
    land on a <b>grid dot</b>.</p>
<svg id="plot" viewBox="0 0 320 280" class="plot"></svg>
<div id="readout" class="readout"></div>
<div class="btns">
  <button id="lp" type="button">Show LP optimum</button>
  <button id="round" type="button">Round it</button>
  <button id="ip" type="button">Integer optimum</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: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.plot { width: 100%; max-width: 440px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.region { fill: #cfe6f0; stroke: #457b9d; stroke-width: 1.5; opacity: .8; }
.axis { stroke: #9aa7b2; stroke-width: 1.5; }
.gp { fill: #b8c4cf; }
.gp.feas { fill: #2a9d8f; }
.lpopt { fill: #e76f51; stroke: #fff; stroke-width: 1.5; }
.ipopt { fill: #0a7d33; stroke: #fff; stroke-width: 2; }
.bad { fill: none; stroke: #c0392b; stroke-width: 3; }
.star { fill: #e76f51; }
.tick { font: 600 10px ui-monospace, monospace; fill: #6a7b88; }
.readout { font: 600 14px system-ui; min-height: 2.6em; line-height: 1.5; margin: .7rem 0 .5rem; }
.readout b { color: #1d3557; }
.readout .r { color: #c0392b; } .readout .g { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .5rem .9rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// A tiny 2-variable integer program: maximize x + y subject to
//   -x + y <= 1,  8x + 2y <= 19,  x,y >= 0.
// LP optimum is fractional (1.7, 2.7); rounding to (2,3) is INFEASIBLE;
// the true integer optimum has value 3 (e.g. (1,2) or (2,1)).
const X0 = 40, Y0 = 250, SX = 80, SY = 55; // axes mapping
const px = (x, y) => [X0 + x * SX, Y0 - y * SY];
function feasible(x, y) { return x >= 0 && y >= 0 && (-x + y) <= 1 + 1e-9 && (8 * x + 2 * y) <= 19 + 1e-9; }
const LP = [1.7, 2.7], LPv = 4.4;
// region polygon vertices (in order)
const REGION = [[0, 0], [0, 1], [1.7, 2.7], [19 / 8, 0]];
let show = '';

function render() {
  let s = '';
  // region
  s += '<polygon class="region" points="' + REGION.map(([x, y]) => px(x, y).join(',')).join(' ') + '"/>';
  // axes
  const o = px(0, 0), xa = px(3, 0), ya = px(0, 4);
  s += '<line class="axis" x1="' + o[0] + '" y1="' + o[1] + '" x2="' + xa[0] + '" y2="' + xa[1] + '"/>';
  s += '<line class="axis" x1="' + o[0] + '" y1="' + o[1] + '" x2="' + ya[0] + '" y2="' + ya[1] + '"/>';
  for (let x = 0; x <= 3; x++) { const p = px(x, 0); s += '<text class="tick" x="' + (p[0] - 3) + '" y="' + (p[1] + 14) + '">' + x + '</text>'; }
  for (let y = 1; y <= 4; y++) { const p = px(0, y); s += '<text class="tick" x="' + (p[0] - 16) + '" y="' + (p[1] + 4) + '">' + y + '</text>'; }
  // grid points
  for (let x = 0; x <= 3; x++) for (let y = 0; y <= 4; y++) {
    const [cx, cy] = px(x, y);
    s += '<circle class="gp' + (feasible(x, y) ? ' feas' : '') + '" cx="' + cx + '" cy="' + cy + '" r="4"/>';
  }
  if (show === 'lp' || show === 'round' || show === 'ip') {
    const [lx, ly] = px(LP[0], LP[1]);
    s += '<circle class="lpopt" cx="' + lx + '" cy="' + ly + '" r="7"/>';
  }
  if (show === 'round') {
    const [rx, ry] = px(2, 3); s += '<circle class="bad" cx="' + rx + '" cy="' + ry + '" r="9"/>';
  }
  if (show === 'ip') {
    [[1, 2], [2, 1]].forEach(([x, y]) => { const [ix, iy] = px(x, y); s += '<circle class="ipopt" cx="' + ix + '" cy="' + iy + '" r="7"/>'; });
  }
  document.getElementById('plot').innerHTML = s;
  const r = document.getElementById('readout');
  if (show === 'lp') r.innerHTML = '<b>LP optimum</b> at (1.7, 2.7), value <b>4.4</b> — but those aren’t whole numbers.';
  else if (show === 'round') r.innerHTML = 'Rounding to <b>(2, 3)</b> lands <span class="r">outside the region</span> (8·2 + 2·3 = 22 &gt; 19). <span class="r">Infeasible!</span>';
  else if (show === 'ip') r.innerHTML = '<span class="g">Integer optimum</span> value <b>3</b>, at (1, 2) or (2, 1). Lower than the LP bound of 4.4 — and nowhere near the rounded point.';
  else r.innerHTML = 'Green dots are feasible whole-number points. Reveal the LP optimum, then try rounding it.';
}

document.getElementById('lp').addEventListener('click', () => { show = 'lp'; render(); });
document.getElementById('round').addEventListener('click', () => { show = 'round'; render(); });
document.getElementById('ip').addEventListener('click', () => { show = 'ip'; render(); });
document.getElementById('reset').addEventListener('click', () => { show = ''; render(); });
render();
Result
Console

Reveal the LP corner, then try the tempting shortcut: round it. The rounded point pops outside the region — infeasible! The real integer optimum is a different, lower point entirely. That gap between "relax and round" and the true answer is the whole difficulty of integer programming in one picture.

The Hard Part

The dividing line runs right between LP and ILP:

  • Linear programming is easy. With continuous variables, the optimum sits at a corner of the feasible region, found in polynomial time (simplex in practice, interior-point in theory).
  • Integer programming is NP-hard. Requiring whole numbers shatters that nice geometry — the integer points form a lattice with no easy corner to jump to.
  • You can't just round. As the demo shows, rounding the LP optimum can land outside the feasible region or far from the best integer point.
  • The toolkit: relax, branch, cut. Solvers start from the LP relaxation (a bound on the answer), then branch and bound — split on a fractional variable (x ≤ 1 vs x ≥ 2) and recurse — sharpened by cutting planes that slice off fractional regions without removing integer points.
  • It's a universal encoder. Knapsack, graph coloring, set cover and more all translate into integer programs — which is why ILP is NP-hard and why one good solver tackles thousands of different problems.

Modern MILP solvers (CPLEX, Gurobi, open-source CBC) are engineering marvels, routinely cracking problems with millions of variables despite the worst-case wall.

Where It Matters

Integer programming is the quiet engine behind enormous real-world decisions:

  • Logistics and routing: vehicle fleets, delivery plans, warehouse operations.
  • Airlines: crew scheduling, fleet assignment, gate planning — classic giant ILPs.
  • Production and supply chain: what to make, where, and when, in whole units.
  • Finance: portfolio selection and capital budgeting with discrete choices.
  • Energy and telecom: unit commitment for power plants, network design.

Because so many planning problems are naturally discrete, integer programming is the lingua franca of operations research — model your problem as an ILP and a world-class solver does the rest.

Conclusion

Integer programming is the grammar that ties this whole site together. Strip away the whole-number requirement and you have easy linear programming; put it back and you have an NP-hard problem flexible enough to encode knapsack, coloring, covering and countless planning tasks.

The lesson is sharp and surprising: the difficulty isn't in the objective or the constraints — it's in the single word integer. And yet, with LP relaxations, branch-and-bound and cutting planes, the solvers built around this idea quietly run airlines, factories and supply chains every day. Hard in theory, indispensable in practice — the story of optimization itself.

Share this article

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

Comments

Loading comments...

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