Maximise a linear objective subject to linear constraints — the most broadly applicable optimisation framework there is, and the one that quietly contains half of Part VI.
A linear program optimises a linear function of real variables subject to linear inequalities. That sounds narrow and is not: maximum flow, shortest paths, bipartite matching, and the assignment problem are all linear programs, and so are resource allocation, blending, scheduling, and portfolio problems throughout industry. Chapter 29 covers the geometry, the simplex algorithm, and duality — the last of which generalises the max-flow min-cut theorem into a principle that applies to every LP.
cᵀx subject to Ax ≤ b and x ≥ 0, where c and x are n-vectors, b is an m-vector, and A is m × n.maximize c₁x₁ + c₂x₂ + … + cₙxₙ
subject to aᵢ₁x₁ + aᵢ₂x₂ + … + aᵢₙxₙ ≤ bᵢ for i = 1..m
xⱼ ≥ 0 for j = 1..nAny LP can be put into this form by mechanical transformations, all of which CLRS spells out:
| If the LP has | Do this |
|---|---|
| A minimisation objective | Negate c and maximise |
| A variable with no sign constraint | Replace x by x′ - x″ with both ≥ 0 |
| An equality constraint | Replace with two inequalities, ≤ and ≥ |
A ≥ constraint | Multiply through by -1 |
Slack form converts every inequality into an equality by introducing a non-negative slack variable measuring how much room is left in that constraint. Slack form is what the simplex algorithm actually manipulates.
aᵢᵀx ≤ bᵢ defines a half-space. Their intersection is a convex region called the feasible region or simplex. The objective cᵀx defines a family of parallel level sets, and optimising means pushing that family as far as it will go while still touching the region.Three outcomes are possible: the LP is infeasible (the region is empty), unbounded (the objective grows without limit), or has a finite optimum.
SIMPLEX, outline
1. Convert to slack form and find an initial feasible vertex
(the INITIALIZE-SIMPLEX subproblem).
2. repeat
choose a nonbasic variable whose increase improves the objective
determine how far it can increase before a constraint binds
pivot: swap that variable into the basis, swap out the binding one
until no nonbasic variable can improve the objective
3. Report the optimal solution.Each pivot is a change of basis, algebraically identical to a step of Gaussian elimination from Chapter 28. The variables split into m basic ones (currently non-zero) and n nonbasic ones (currently zero), and each basis corresponds to one vertex.
| Algorithm | Worst case | In practice |
|---|---|---|
| Simplex | Exponential (Klee-Minty cubes) | Excellent — usually O(m) pivots |
| Ellipsoid (Khachiyan 1979) | Polynomial | Slow; of theoretical importance only |
| Interior point (Karmarkar 1984) | Polynomial | Competitive, better on very large problems |
2ⁿ vertices of a distorted cube, but such inputs essentially never arise. The ellipsoid method settled the theoretical question — LP is in P — without displacing simplex in practice. Modern solvers ship both simplex and interior-point and choose per problem.The deepest idea in the chapter. Every LP (the primal) has a companion LP (the dual) built by transposing its structure.
PRIMAL DUAL
maximize cᵀx minimize bᵀy
subject to Ax ≤ b subject to Aᵀy ≥ c
x ≥ 0 y ≥ 0| Primal | Dual |
|---|---|
n variables | n constraints |
m constraints | m variables |
| Maximise | Minimise |
Objective coefficients c | Constraint bounds c |
Constraint bounds b | Objective coefficients b |
x and any feasible dual y, cᵀx ≤ bᵀy. Every feasible dual solution is an upper bound on every feasible primal solution.x*, then the dual has an optimal solution y*, and cᵀx* = bᵀy*. The two optima are equal.v proves no primal solution exceeds v. Anyone can verify the proof without rerunning the algorithm. That turns “trust my optimiser” into a checkable claim, and it is why LP solvers report dual values alongside the answer.| Problem | As a linear program |
|---|---|
| Maximum flow | Variables are edge flows; constraints are capacities and conservation; maximise the flow out of s. |
| Shortest paths | Maximise dₜ subject to dᵛ ≤ dᵘ + w(u,v) for every edge — the triangle inequality as constraints. |
| Minimum-cost flow | Flow constraints plus a linear cost objective. No purely combinatorial algorithm is as simple. |
| Assignment problem | Chapter 25’s Hungarian algorithm is a specialised primal-dual LP method. |
| Difference constraints | Chapter 22 solved these with Bellman-Ford; they are an LP feasibility problem. |
| Vertex cover, set cover | Their LP relaxations drive the approximation algorithms of Chapter 35. |
The standard response is LP relaxation: drop the integrality requirement, solve the resulting LP, and then either round the answer or search around it with branch-and-bound. The relaxation’s optimum bounds the integer optimum, which is exactly what branch-and-bound needs to prune, and how far apart they are is the integrality gap. Chapter 35 uses relaxation and rounding to build approximation algorithms with proven quality guarantees.
cᵀx subject to Ax ≤ b, x ≥ 0. Every LP converts to it mechanically. Slack form is what simplex manipulates.Chapter 30 turns to polynomials and the fast Fourier transform, which multiplies two degree-n polynomials in Θ(n lg n) instead of Θ(n²) by switching representation — a divide-and-conquer result as surprising as Strassen’s and vastly more used.