Helpful context:

A hospital needs to schedule 50 nurses across three shifts. The constraints pile up quickly: no nurse works two consecutive night shifts, every shift needs at least 8 nurses, certain nurses can’t be rostered together, some nurses are only available on certain days. Write it all out and you have a system of linear inequalities - which is perfectly fine, linear programs are solvable in polynomial time. But there is one more requirement: you cannot schedule 0.3 of a nurse. All variables must be whole numbers.

That single word - integer - is the difference between polynomial and NP-hard. It is also the difference between a textbook exercise and the optimization engine inside every airline, supply chain, and logistics company you’ve ever interacted with. Integer linear programming (ILP) is the most widely used optimization model in industry and one of the most technically deep in theory.

Linear Programs and the LP Relaxation

A linear program (LP) is an optimization problem where the objective and all constraints are linear:

$$\max; c^T x \quad \text{subject to} \quad Ax \leq b,\quad x \geq 0.$$

This is solvable in polynomial time - the simplex method, interior-point methods, and ellipsoid method all work. An ILP adds the constraint that $x \in \mathbb{Z}^n$: the variables must be integers.

The LP relaxation is what you get when you drop the integrality constraint and allow $x \in \mathbb{R}^n$. It’s solvable in polynomial time and gives you a useful bound. If the LP relaxation’s optimal solution happens to be integral, you’re done - you’ve solved the ILP for free. If not, you have a fractional solution that you need to round or branch into an integral one.

The LP relaxation is always at least as good as the ILP optimum (since we’re optimizing over a larger set), so it serves as an upper bound (for maximization) on what any integer solution can achieve.

The Integrality Gap

The integrality gap is how much you lose by requiring integrality:

$$\text{gap} = \frac{OPT_{LP}}{OPT_{ILP}} \geq 1.$$

For some problems the gap is exactly 1 - the LP relaxation automatically produces integer solutions. For others, the gap can be arbitrarily large. A clean example: vertex cover.

Vertex cover ILP. Given a graph $G = (V, E)$, find the smallest subset $S \subseteq V$ such that every edge has at least one endpoint in $S$. Write it as:

$$\min \sum_{v} x_v \quad \text{s.t.} \quad x_u + x_v \geq 1 \text{ for each edge } (u,v), \quad x_v \in \{0,1\}.$$

The LP relaxation allows $x_v \in [0, 1]$. On any graph, setting $x_v = 1/2$ for all $v$ is always feasible (every edge constraint is satisfied with equality). So the LP relaxation has value $n/2$. On a graph whose minimum vertex cover has size $n/2 + 1$ (e.g., a certain dense random graph), the gap is close to 1 - not dramatic. But on a $k$-clique, the LP gives $k/2$ while you need all $k-1$ vertices, giving a gap of $(k-1)/(k/2) \to 2$. The integrality gap for vertex cover ILP is 2.

This gap matters: it limits how good any LP-rounding-based approximation algorithm can be, and it tells you how much information the LP relaxation captures about the ILP.

Branch and Bound

Branch and bound is the backbone of every modern ILP solver. The idea: explore a tree of increasingly constrained LPs, using LP bounds to prune branches that can’t improve on the best integer solution found so far.

The algorithm:

  1. Solve the LP relaxation. If the solution is integer, record it as the incumbent. If the LP is infeasible, stop (infeasible ILP).
  2. If the LP optimal value is worse than the current incumbent, prune this branch.
  3. Otherwise, pick a fractional variable $x_i^* \notin \mathbb{Z}$. Branch: create two child subproblems:
    • Left: add constraint $x_i \leq \lfloor x_i^* \rfloor$
    • Right: add constraint $x_i \geq \lceil x_i^* \rceil$
  4. Recurse on both children.

The LP at each node provides an upper bound on what any integer solution in that subtree can achieve. If this bound is below the current best integer solution, there’s no point exploring further - prune.

The key insight is that LP bounds get tighter as we add constraints. Deep in the tree, the LP relaxation at each node is forced to be close to integral, so the bounds become very informative.

Variable selection - which fractional variable to branch on - profoundly affects performance. Branching on variables with fractional values close to 0.5 tends to produce balanced trees. Node selection - which open node to explore next - is equally important. Best-first (explore the node with the highest LP bound) uses more memory but finds good solutions quickly. Depth-first uses less memory but may get stuck in bad branches. Modern solvers blend both.

Cutting Planes

Instead of branching, you can add linear constraints that cut off the fractional solution without removing any integer-feasible points. These are called cutting planes or cuts.

The idea: the LP feasible region (a polytope) contains the integer feasible region, but they’re not equal. We want to tighten the polytope by slicing off the fractional corners, making the LP feasible region closer to the convex hull of integer points.

Gomory cuts are a systematic way to generate cuts from the simplex tableau. If a basic variable $x_i$ has fractional value $\bar{x}_i = \lfloor \bar{x}_i \rfloor + f_i$ where $0 < f_i < 1$, and the corresponding tableau row is $x_i = \bar{x}i - \sum_j \bar{a}{ij} x_j$, then the Gomory cut is:

$$\sum_j f(\bar{a}_{ij}) x_j \geq f_i$$

where $f(a) = a - \lfloor a \rfloor$ is the fractional part. This cut is satisfied by all integer-feasible solutions (you can verify this by case analysis) but violated by the current fractional LP optimum. Add it and re-solve the LP. Repeat.

Gomory proved that finitely many such cuts eventually produce an integer solution, for rational data. In practice, the convergence can be slow - cutting planes alone are rarely competitive - but combined with branch and bound, they are essential.

Branch and cut interleaves branching and cutting: at each node in the branch-and-bound tree, solve the LP, add violated cuts (tightening the bound), then branch if still fractional. Modern solvers generate a rich variety of cuts - Mixed-Integer Rounding (MIR) cuts, lift-and-project cuts, problem-specific cuts - and choosing which cuts to add when is itself a learned art.

Totally Unimodular Matrices

For some problems, the integrality gap is exactly 1 - the LP relaxation always produces integer solutions. This is not a coincidence; it follows from the structure of the constraint matrix.

A matrix $A$ is totally unimodular (TU) if every square submatrix has determinant $0$, $+1$, or $-1$.

Discomfort check. Why does TU imply integrality? A basic feasible solution to $Ax \leq b$, $x \geq 0$ corresponds to a vertex of the polytope, which is the solution to a square subsystem $A' x = b'$. If $A'$ is a square submatrix of $A$ with determinant $\pm 1$, then by Cramer’s rule $x = (A')^{-1} b'$ has integer entries whenever $b'$ is integer. So every vertex of the LP feasible polytope is an integer point - meaning the LP optimum is always achieved at an integer point.

Which matrices are TU? Two beautiful families:

Bipartite graph incidence matrices. The vertex-edge incidence matrix of a bipartite graph (rows = vertices, columns = edges, $A_{ve} = 1$ if vertex $v$ is an endpoint of edge $e$) is TU. This means bipartite matching, assignment problems, and bipartite covering problems can all be solved as LPs - no branch and bound needed. The LP relaxation automatically gives integer solutions.

Network flow matrices. The constraint matrix for any min-cost flow problem on a directed graph is TU. This is why shortest path, maximum flow, and transportation problems are all polynomial - even though they look like ILPs, the LP relaxation is always integral.

Interval matrices. Many scheduling-on-intervals problems have TU constraint matrices. When you can encode your problem as a network flow or bipartite matching, you’re in polynomial time. When you can’t, you’re in branch-and-bound territory.

Discomfort check. ILP is NP-hard but commercial solvers (Gurobi, CPLEX) solve problems with millions of variables. How?

The theory says worst case is hard. Practice says most real problems have structure - network structure, sparsity, near-TU constraint matrices - that solvers exploit aggressively. Branch-and-bound with learned branching rules, dozens of cut types generated at each node, primal heuristics that find good integer solutions early, and parallel search across many nodes. Modern solvers also use machine learning to tune their own parameters. The gap between theory (exponential worst case) and practice (seconds to minutes for industrial instances) is one of the most striking in all of optimization.

Applications

ILP is not a theoretical curiosity - it is the workhorse of operations research.

Airline crew scheduling. Assign flight crews to flights so that every flight is covered, crew rest requirements are met, no crew flies too many hours, and costs are minimized. This is a set covering / partitioning ILP with hundreds of thousands of binary variables. Airlines run these solvers daily.

Supply chain optimization. Decide which factories to build (binary), how much to produce at each (continuous), which routes to use (binary or continuous). Mixed-integer programs with both integer and continuous variables.

VLSI design. Place circuit components and route wires to minimize area and wire length. Quadratic assignment and routing subproblems solved via ILP with problem-specific cuts.

Protein structure prediction. Side-chain placement and rotamer selection: choose one rotamer per residue (binary variables) to minimize pairwise energy. Huge binary ILP, solved by branch and cut with LP bounds.

Summary

Concept What it means
LP relaxation Drop integrality constraints; solvable in polynomial time
Integrality gap How much LP optimum can exceed ILP optimum
Branch and bound Tree search using LP bounds to prune; exponential worst case
Gomory cuts Linear constraints cutting off fractional LP vertices
Branch and cut Interleave cutting and branching; how modern solvers work
Totally unimodular TU constraint matrix guarantees LP gives integer solutions
TU examples Bipartite graphs, network flows, interval scheduling

ILP is simultaneously NP-hard in theory and routine in practice. The integrality gap tells you how much you lose by relaxing. Branch and bound navigates the integer feasible region using LP bounds as a flashlight. TU matrices reveal the beautiful cases where LP and ILP agree. And cutting planes tighten the polytope until fractional solutions have no more room to hide.

Read next: