Prerequisite: Linear Programming

Overview

Integer Linear Programming (ILP) extends linear programming by requiring some or all decision variables to take integer values. The canonical form is:

$$\max; c^T x \quad \text{subject to}\quad Ax \leq b,\quad x \in \mathbb{Z}_{\geq 0}^n$$

This small change - integers instead of reals - turns a tractable problem into an NP-hard one. Yet ILP is also the modelling language of combinatorial optimisation: scheduling, routing, network design, and resource allocation all reduce naturally to ILP. Modern solvers (Gurobi, CPLEX, SCIP) routinely solve instances with millions of variables through a combination of branch-and-bound, cutting planes, and LP relaxations.

Why ILP Is NP-Hard

Reduction from Subset Sum. Given integers $a_1, \ldots, a_n$ and target $T$, ask whether there exists a subset summing to $T$. Encode this as:

$$\max; 0 \quad \text{s.t.}\quad \sum_{i=1}^n a_i x_i = T,\quad x_i \in {0,1}$$

If a feasible solution exists, the answer is yes. This is a 0-1 ILP with one constraint. Since Subset Sum is NP-complete, ILP is NP-hard in general. The hardness sits entirely in the integrality requirement - without it the problem is solvable in polynomial time.

LP Relaxation and the Integrality Gap

The LP relaxation of an ILP is obtained by dropping the integrality constraint, replacing $x \in \mathbb{Z}^n$ with $x \in \mathbb{R}_{\geq 0}^n$. It can be solved in polynomial time via the simplex method or interior-point methods.

The integrality gap measures how much optimality is lost:

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

For maximisation problems. A small gap means the LP relaxation is a good guide to the ILP solution. For some problems - bipartite matching, shortest paths, network flows - the gap is exactly 1, meaning the LP relaxation always returns an integer solution (see Total Unimodularity below). For others like the Travelling Salesman Problem, the gap can be large.

Branch and Bound

Branch and bound is the backbone of all modern ILP solvers. The algorithm maintains a search tree where each node represents an ILP with additional constraints.

Algorithm:

  1. Solve the LP relaxation. If the solution is already integer, record it as the incumbent.
  2. If the LP is infeasible, prune this branch.
  3. If the LP optimal value is below the best known integer solution (the bound), prune.
  4. Otherwise, select a fractional variable $x_i^\ast \notin \mathbb{Z}$. Branch by creating two subproblems:
    • Left child: add constraint $x_i \leq \lfloor x_i^\ast \rfloor$
    • Right child: add constraint $x_i \geq \lceil x_i^\ast \rceil$
  5. Recurse on both children.

The LP relaxation at each node provides an upper bound on the best integer solution reachable in that subtree - which is used to prune the tree aggressively. The key insight is that $OPT_{LP}(S) \geq OPT_{ILP}(S)$ for any subproblem $S$, because the LP feasible region contains the ILP feasible region.

Variable selection (branching rule) and node selection (best-first vs. depth-first) dramatically affect performance. State-of-the-art solvers use learned branching heuristics.

Cutting Planes

Cutting plane methods add constraints that cut off fractional LP solutions without removing any integer-feasible points.

Chvátal-Gomory Cuts

For any non-negative linear combination $u^T(Ax \leq b)$, take the integrality of $x$ to tighten: if $u^T A \in \mathbb{Z}^n$, then $u^T A x \leq \lfloor u^T b \rfloor$ is valid for all integer $x$.

Gomory Cuts

Applied to the final simplex tableau. If basic variable $x_i$ has fractional value $\bar{x}_i = \lfloor \bar{x}_i \rfloor + f_i$, $0 < f_i < 1$, and the tableau row is $x_i = \bar{x}i - \sum_j \bar{a}{ij} x_j$, 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 but violated by the current LP optimum. Adding it and re-solving eventually yields an integer solution after finitely many iterations (for rational data).

Branch and Cut

Modern solvers combine both approaches: at each node, solve the LP relaxation, add violated cutting planes (strengthening the bound), then branch. Crucially, cuts are generated locally at nodes where they are most effective. The cutting planes used in practice include Mixed-Integer Rounding (MIR) cuts, lift-and-project cuts, and problem-specific cuts like subtour elimination constraints for TSP.

Total Unimodularity

A matrix $A$ is totally unimodular (TU) if every square submatrix has determinant $0$, $+1$, or $-1$. For TU constraint matrices with integer $b$, every vertex of the LP feasible polytope ${x : Ax \leq b, x \geq 0}$ is an integer vector. Consequently, the LP relaxation always attains its optimum at an integer point - so solving the LP solves the ILP exactly, in polynomial time.

Key TU matrices:

  • Bipartite graphs: The vertex-edge incidence matrix of any bipartite graph is TU. This means bipartite matching and assignment problems are solvable by LP alone.
  • Network flow: Constraint matrices for min-cost flow and shortest-path problems are TU, so integer flows arise naturally from LP.
  • Interval matrices: Constraint matrices from scheduling on interval graphs are TU.

Complexity Summary

Approach Worst-case time Notes
LP relaxation Polynomial May have integrality gap
Branch and bound Exponential Practical with good bounds
Cutting planes Exponential Finite convergence guaranteed
TU structure Polynomial Exact via LP

Examples

Job scheduling with integer constraints. Assign $n$ jobs to $m$ machines to minimise makespan. Each job can be split into tasks with machine-specific processing times. Binary variables $x_{ij} \in {0,1}$ indicate assignment; auxiliary variables capture the makespan. Branch and cut handles hundreds of jobs in practice.

Facility location. Given candidate facility sites and customer demand points, decide which facilities to open (binary $y_j$) and how to assign customers to facilities (continuous $x_{ij}$) to minimise opening costs plus service costs. The LP relaxation provides a $1 - 1/e$ approximation; the exact ILP is solved by branch and cut.

Bin packing. Pack items of sizes $s_1, \ldots, s_n$ into bins of capacity $C$ using the minimum number of bins. Binary variables $x_{ij}$ indicate item $i$ in bin $j$; binary $y_j$ indicates bin $j$ is used. The LP relaxation has a well-known integrality gap: $OPT_{LP}$ can be as small as $OPT_{ILP}/2$. Cutting planes based on conflict cliques tighten the relaxation significantly.

Set cover. Select a minimum-weight subset of sets $S_1, \ldots, S_m$ that covers all elements. Binary variable $x_j = 1$ if $S_j$ is selected. The greedy algorithm gives an $O(\log n)$ approximation; the ILP finds the exact optimum via branch and cut.

Read Next: Approximation Algorithms