Integer Programming: Branch & Bound & Cutting Planes

Integer programming extends LP by requiring some or all variables to take integer values. This single constraint transforms polynomial-time LP into an NP-hard problem — but branch-and-bound with cutting planes makes large instances tractable in practice by combining LP relaxation bounds with intelligent search.

Concepts

Adding a single constraint — "some variables must be integers" — transforms polynomial-time LP into NP-hard ILP. The feasible region is no longer a convex polytope but a discrete lattice of points; the LP relaxation gives a lower bound, and the gap between this relaxation and the true integer optimum determines how much search is required. Branch-and-bound uses LP bounds to prune this search, while cutting planes tighten the relaxation by slicing off fractional vertices.

ILP Formulation

A mixed-integer linear program (MILP) has the form:

When all integer variables are binary ($x_j \in \{0, 1\}$), the problem is a binary integer program (BIP). ILP is NP-hard in general: 3-SAT reduces to BIP by encoding clauses as linear constraints.

The integrality constraint $x_j \in \mathbb{Z}$ is the minimal change from LP that encodes combinatorial choice. Without it, every yes/no decision becomes a continuous dial — and the LP optimum simply sets that dial to a fraction. The formulation forces the solver to commit: a variable is either included or not, a route is taken or skipped. That commitment is what makes ILP expressive enough to encode SAT, and exactly what makes it NP-hard.

LP Relaxation and Integrality Gap

The LP relaxation drops the integrality constraints, replacing $x_j \in \mathbb{Z}$ with $x_j \geq 0$. Let $z_{LP}$ be its optimal value and $z_{ILP}$ the integer optimum. Then:

The integrality gap is $z_{ILP} / z_{LP}$ (or $z_{LP} / z_{ILP}$ for maximization). A tight LP relaxation means a small gap and a strong bound for branch-and-bound.

The LP relaxation gives the continuous optimum; integer solutions are the lattice points at vertices of the feasible region. The convex hull of all integer-feasible points is the integer hull — if we could optimize over it directly (a tighter LP), we would get the ILP optimum immediately. Cutting planes approximate the integer hull.

Branch-and-Bound

Branch-and-bound maintains a search tree where each node is an LP relaxation with additional variable bounds.

Algorithm:

1. Solve the LP relaxation at the root. If the solution is integer-valued, done.
2. Branch: pick a fractional variable $x_j^* \notin \mathbb{Z}$. Create two child nodes by adding constraints $x_j \leq \lfloor x_j^* \rfloor$ (left child) and $x_j \geq \lceil x_j^* \rceil$ (right child).
3. Bound: at each node, solve the LP relaxation. If its objective $z_{\text{node}} \geq z_{\text{best}}$ (current best integer solution), prune the subtree — no integer solution here can improve on what we have.
4. Fathom: if the LP relaxation is infeasible, prune. If it gives an integer solution better than $z_{\text{best}}$, update the incumbent.

The key insight: each node's LP relaxation lower-bounds every integer solution reachable in that subtree. Tight LP bounds lead to aggressive pruning and small trees.

Cutting Planes

A cutting plane (or cut) is a valid inequality $\pi^\top x \leq \pi_0$ satisfied by all integer-feasible points but violated by the current LP relaxation solution. Adding cuts tightens the LP relaxation toward the integer hull without branching.

Gomory cut: Given a row of the optimal simplex tableau corresponding to a fractional basic variable:

Write $\bar{a}_{ij} = \lfloor \bar{a}_{ij} \rfloor + f_{ij}$ and $\bar{b}_i = \lfloor \bar{b}_i \rfloor + f_i$ with $0 < f_i < 1$. The Gomory cut is:

This is valid for all integer solutions (since $x_j \in \mathbb{Z}$ implies the sum is an integer, and if less than 1 it must be $\leq 0$, contradicting $f_i > 0$) but violated by the current LP solution where the sum equals $f_i - f_i = 0 < f_i$. Wait — more precisely, the current LP solution satisfies the row equation with fractional $\bar{b}_i$, so the fractional parts satisfy $\sum f_{ij} x_j = f_i$ only if $x_j$ are at their LP values. Any integer solution must have the left side as a non-negative integer, so at least $\lceil f_i \rceil = 1 > f_i$... or zero. Since $f_i > 0$, the cut forces $\sum f_{ij} x_j \geq f_i$ which eliminates the current LP vertex.

Repeated Gomory cuts provably converge to the integer hull in finite steps, though convergence can be slow in practice. Commercial solvers use problem-specific cuts (clique cuts, cover cuts, flow cuts) alongside Gomory cuts.

Modeling Tricks

Big-M constraints encode logical implications. To force $y = 1 \Rightarrow x \leq b$:

When $y = 0$, the constraint becomes $x \leq b + M$, which is inactive if $M$ is large enough. Choosing $M$ too large weakens the LP relaxation; too small makes the model infeasible. A good bound from problem structure is always preferable.

Linearizing a product. To linearize $z = x_1 x_2$ with $x_1 \in \{0,1\}$ and $x_2 \in [0, U]$:

These four constraints force $z = x_1 x_2$ exactly for binary $x_1$.

Worked Example

0/1 Knapsack by Branch-and-Bound

Four items with weights $w = (2, 3, 4, 5)$, values $v = (3, 4, 5, 6)$, capacity $W = 8$.

ILP formulation:

LP relaxation (root): Solve continuously. Greedy by value/weight: item 1 ($3/2=1.5$), item 2 ($4/3=1.33$), item 3 ($5/4=1.25$), item 4 ($6/5=1.2$). Take items 1, 2 fully (weight 5), then $3/4$ of item 3. Objective: $3 + 4 + 3.75 = 10.75$. $x_3 = 0.75$ is fractional.

Branch on $x_3$:

• Left branch ($x_3 = 0$): LP relaxation over items 1, 2, 4 with capacity 8. Take 1, 2 (weight 5), then $3/5$ of item 4. Obj: $3 + 4 + 3.6 = 10.6$. Fractional $x_4$.
  • Branch on $x_4$: left ($x_4 = 0$) gives integer solution $\{x_1, x_2\}$, value = 7. Right ($x_4 = 1$): weight constraint $2x_1 + 3x_2 \leq 3$; best integer: $x_2=1$, value = $4 + 6 = 10$. Incumbent = 10.
• Right branch ($x_3 = 1$): Remaining capacity 4. LP over items 1, 2, 4. Take item 1 (weight 2), then $2/5$ of item 4. Obj: $5 + 3 + 2.4 = 10.4 > 10$; explore. Branch on $x_4$: right ($x_4 = 1$, weight 5 > 4, infeasible). Left ($x_4 = 0$): items 1, 2 in capacity 4. Take $x_1 = 1, x_2 = 2/3$ fractional. Branch: $x_2 = 0 \Rightarrow$ value $= 5 + 3 = 8 < 10$, prune. $x_2 = 1$: weight $2 + 3 + 4 = 9 > 8$, infeasible.

Optimal: $x_2 = 1, x_4 = 1$, value = 10.

Gomory Cut

After the LP relaxation gives $x_3 = 0.75$ at the root, the simplex tableau row for $x_3$ is (schematically):

Here $f_3 = 0.75$, $f_{s_1} = 0.5$. The Gomory cut is $0.5 s_1 \geq 0.75$, i.e., $s_1 \geq 1.5$, i.e., $2x_1 + 3x_2 + 4x_3 + 5x_4 \leq 6.5$. This cut tightens the LP relaxation and eliminates the fractional solution.

Connections

Where Your Intuition Breaks

Branch-and-bound sounds like exhaustive search with pruning — but the pruning is doing almost all the work. On well-structured problems (tight LP relaxations, good incumbent solutions found early), commercial solvers prune 99.99% of the tree and solve million-variable instances in seconds. On adversarial instances (poorly-constructed Big-M models, near-integer LP relaxations with many fractional variables), the tree explodes exponentially and the same solver stalls. The misconception is that NP-hardness means "always slow in practice." It means "worst-case exponential" — and the solver's entire engineering effort goes into making the worst case rare by tightening bounds, finding incumbents early via primal heuristics, and adding cuts that eliminate fractional vertices without branching.

Complexity and Tractability

ILP is NP-hard in general, but not all instances are hard. Problem structure matters enormously:

Big-M Sensitivity

Branch-and-Cut in Practice

Modern ILP solvers (Gurobi, CPLEX, HiGHS) use branch-and-cut: integrate cutting planes at every node of the branch-and-bound tree, not just at the root. Combined with strong branching (evaluate several candidate branching variables), primal heuristics for fast incumbents, and diving strategies, commercial solvers routinely solve instances with millions of variables and constraints in minutes — despite worst-case NP-hardness.