Integer Linear Programming
Motivation
Many discrete optimization problems — vertex cover, knapsack, set cover, scheduling, assignment, network design — admit a clean expression as “minimize a linear cost subject to linear constraints, with the variables required to take integer values.” This template is integer linear programming (ILP), and it is expressive enough to encode any NP-complete problem yet structured enough that industrial solvers (CPLEX, Gurobi) routinely tackle instances with millions of variables (Kleinberg and Tardos 2005; Cormen et al. 2009).
ILP sits at a sweet spot for practitioners: it is a single, mature language for stating combinatorial problems, with off-the-shelf solvers powerful enough that “just write it as an ILP” is often the right first attempt. Understanding why ILP is hard — and why its continuous relaxation is easy — is the gateway to LP relaxation and approximation algorithms.
Standard form
An integer linear program is \[ \begin{aligned} \text{maximize} \quad & c^\top x \\ \text{subject to} \quad & A x \le b \\ & x \in \mathbb{Z}^n. \end{aligned} \] \(c \in \mathbb{R}^n\) is the cost vector, \(A \in \mathbb{R}^{m \times n}\) and \(b \in \mathbb{R}^m\) define \(m\) linear constraints, and the variables \(x_1, \dots, x_n\) are required to be integers.
A common restriction is 0/1 integer linear programming, where \(x_i \in \{0, 1\}\) for every \(i\). The 0/1 form is just as expressive — any bounded integer variable can be replaced by a binary expansion — and is the form most commonly used in modelling.
Example: a 2-D ILP
The same 2-variable LP from the linear programming article — maximize \(3x_1 + 2x_2\) subject to \(2x_1 + 2x_2 \le 9\), \(x_1 \le 3\), \(x_2 \le 3\), \(x_1, x_2 \ge 0\) — with integrality added. The shaded pentagon is the LP relaxation feasible region; the gray dots are the 13 feasible integer points that make up the ILP feasible set.
The LP relaxation optimal \((3, \tfrac{3}{2})\) is not an integer point. The best feasible integer solution is \((3, 1)\), with objective value \(11\) versus the LP’s \(12\) — an integrality gap of \(1\). Note that rounding \(x_2\) up to \(2\) would give \((3, 2)\), which violates \(2x_1 + 2x_2 \le 9\), so naive rounding can be infeasible.
Modelling examples
Vertex cover. Given graph \(G = (V, E)\), find a smallest \(S \subseteq V\) such that every edge has at least one endpoint in \(S\): \[ \min \sum_{v \in V} x_v \quad \text{s.t.} \quad x_u + x_v \ge 1 \; \forall (u, v) \in E, \quad x_v \in \{0, 1\}. \]
0/1 knapsack (detail). \[ \max \sum_i v_i x_i \quad \text{s.t.} \quad \sum_i w_i x_i \le W, \quad x_i \in \{0, 1\}. \]
Set cover. Given a universe \(U\) and subsets \(S_1, \dots, S_m \subseteq U\), find a minimum-cost collection of subsets covering \(U\): \[ \min \sum_j c_j x_j \quad \text{s.t.} \quad \sum_{j : u \in S_j} x_j \ge 1 \; \forall u \in U, \quad x_j \in \{0, 1\}. \]
Travelling salesman (with the Miller-Tucker-Zemlin formulation, polynomial-size constraints): a 0/1 variable per directed edge, flow-conservation constraints, and subtour-elimination via auxiliary integer variables.
The pattern: identify the discrete decision (include vertex? pick set? traverse edge?), introduce a binary indicator, and translate combinatorial constraints into linear inequalities.
Example: set-cover ILP with four sets
Universe \(U = \{1, 2, 3, 4\}\). Four candidate sets with costs:
| Set | Elements | Cost |
|---|---|---|
| \(S_1\) | \(\{1, 2\}\) | \(3\) |
| \(S_2\) | \(\{2, 3\}\) | \(2\) |
| \(S_3\) | \(\{3, 4\}\) | \(2\) |
| \(S_4\) | \(\{1, 4\}\) | \(4\) |
Introduce binary variable \(x_j \in \{0, 1\}\) indicating whether \(S_j\) is selected. Write one covering constraint per element:
\[ \min\ 3x_1 + 2x_2 + 2x_3 + 4x_4 \] \[ \text{s.t.}\quad x_1 + x_4 \ge 1 \quad (\text{element 1}) \] \[ x_1 + x_2 \ge 1 \quad (\text{element 2}) \] \[ x_2 + x_3 \ge 1 \quad (\text{element 3}) \] \[ x_3 + x_4 \ge 1 \quad (\text{element 4}) \] \[ x_j \in \{0, 1\}. \]
The solution \(x_1 = 1\), \(x_3 = 1\) (select \(S_1\) and \(S_3\)) covers all four elements: \(S_1 \cup S_3 = \{1,2\} \cup \{3,4\} = U\), with cost \(3 + 2 = 5\). Selecting \(S_2\) and \(S_4\) instead also covers \(U\) (\(\{2,3\} \cup \{1,4\} = U\)) at cost \(2 + 4 = 6\), so \(\{S_1, S_3\}\) is preferable. No single set covers \(U\), so cost \(< 5\) is infeasible; the ILP optimum is \(5\).
Why ILP is hard
ILP is NP-hard, even in the very restricted 0/1 case. The proof is a direct reduction from 3-SAT (or equivalently from any of the standard NP-complete problems): given a SAT instance, encode each variable as a 0/1 ILP variable and each clause as a linear inequality. (proof)
So a polynomial-time algorithm for ILP would solve every problem in NP in polynomial time. Existence of such an algorithm would prove \(\mathsf{P} = \mathsf{NP}\).
Why the LP relaxation is easy
Drop the integrality constraint \(x \in \mathbb{Z}^n\) and replace it with \(x \in \mathbb{R}^n\). The result is a linear program, solvable in polynomial time (interior-point methods, ellipsoid method).
The LP relaxation gives an upper bound on the ILP optimum (for maximization) — a strict relaxation can only allow more solutions, so its optimum is at least as large. The gap between the ILP optimum and the LP optimum is the integrality gap, and it controls how good a solution we can recover by rounding. In the 2-D example above, the LP relaxation feasible region is the shaded pentagon and the ILP feasible set is the 13 integer dots; the LP optimum \((3, \tfrac{3}{2})\) is fractional, and the best integer solution \((3, 1)\) achieves objective value \(11\) versus the LP’s \(12\) — an integrality gap of \(1\).
For some problems the LP relaxation has integer optima automatically: when the constraint matrix \(A\) is totally unimodular (every square submatrix has determinant in \(\{-1, 0, 1\}\)), every basic feasible LP solution is integer. Bipartite matching, network flow, and shortest paths all enjoy this property, which is why they are polynomial-time despite being expressible as ILPs.
How ILP is solved in practice
Modern solvers combine many techniques:
- Branch and bound: at each node, solve the LP relaxation; if the relaxation is fractional, branch by fixing some variable to 0 or 1; prune nodes whose LP bound is worse than the best integer solution found so far.
- Cutting planes: add new linear inequalities (Gomory cuts, Chvátal-Gomory cuts) that are valid for all integer solutions but cut off the current fractional LP optimum.
- Branch and cut: combine the two; cuts tighten the relaxation at every node.
- Heuristics for primal solutions: rounding, local search, large-neighbourhood search.
- Presolve / preprocessing: detect implied bounds, redundant constraints, dominated variables.
For the worst case the running time is exponential, but on real instances solvers routinely handle problems with millions of variables and constraints, and the gap between theoretical worst-case and practical performance is enormous.
When to use ILP
- The problem is genuinely combinatorial: integer-valued decisions matter.
- An exact (or near-exact) solution is needed.
- Problem size is moderate (thousands to millions of variables, depending on structure).
- A natural linear formulation exists.
When ILP is too expensive, the next moves are: solve the LP relaxation and round, apply problem-specific approximation algorithms, or fall back on heuristics like local search or multiplicative weights.