Duality — the series

Two polytopes, two optima, one number. The feasible regions of a linear program and of its dual, side by side, each with its optimal vertex, and a number line on which the gap between the two optima closes to nothing.

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

part 1 · applied

What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

A linear program and its dual reach the same number. What the dual's variables are is a separate question, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

part 2 · applied

The duality theorem's four cases, counted over 6,561 small programs. A three-by-three table crossing the status of a linear program — optimal, unbounded or infeasible — with the status of its dual, counting every small program with coefficients from minus one to one. Five of the nine cells are empty.

When one of the two numbers is missing

The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.

part 3 · applied

The optimum as the lowest of 3 lines, one per dual vertex. The optimal value of a linear program plotted against one right-hand side, drawn over a family of straight lines, one for each vertex of the dual feasible region. The optimum follows the lowest line throughout.

The lines the optimum lies under

Change the resources a linear program is given and its best value changes too, tracing a graph. Every solution of the dual is a straight line lying above that graph, and the graph is exactly the lowest of those lines — a bent roof of finitely many planks. Require the answer to be in whole numbers and the roof stays where it was while the graph falls away beneath it in steps, and the space between is the part of the problem no price can see.

part 4 · applied

3 moves along the edges to the corner that maximises 2x₁ + 3x₂. The simplex method on a two-variable program with 5 constraints, started at the origin. It visits (0, 0), (0, 8), (1, 8), (5/2, 15/2), with objective values 0, 24, 26, 55/2, and stops where the prices on both binding constraints are non-negative.

Prices at every corner

The duality theorem says a linear program's best value equals its dual's, and says nothing about how to find either. The simplex method finds both at once — it walks from corner to corner, and at each one asks the constraints that meet there for prices. A negative price names an edge that climbs; when none is negative, the prices are the proof.

part 5 · applied

Eight corners of a squashed cube, visited in order by the simplex method. Klee and Minty's program in 3 variables drawn as its own deformed cube and as a plain one. The simplex method with the largest-price rule visits all 8 corners, with objective values 0, 4, 6, 10, 15, 19, 21, 25; the optimum is one edge from the start.

The cube that takes every corner

The simplex method is fast on every program anybody meets in practice. In 1972 Victor Klee and George Minty squashed a cube so that the method, choosing the steepest edge each time, visits all of its corners — 2ⁿ − 1 moves in n variables, with the optimum one edge from the start.

part 6 · applied

Two triangles and three paths: the relaxation against the shortest tour. k = 3: 12 cities; subtour relaxation 12 with 6 half-edges; shortest tour 14; ratio 1.167.

A bound that may be off by a third

The shortest tour through a set of cities is hard to find, and a linear programme gives a lower bound for it in polynomial time: give every road a weight between nought and one, two at each city, at least two across every division of the map. On random cities the bound is almost always exact. On two triangles joined by three long paths it falls short by nearly a third, and whether a third is the worst it can ever do has been conjectured for decades and never proved.

part 7 · applied

Christofides' algorithm: tree, pairing, tour. 12 cities: tree 2.4441, 6 odd cities paired for 1.5306, tour 3.6069, shortest 3.4606.

Tours within half again of the best

Nobody can find the shortest tour through many cities quickly, but a tour at most half as long again as the best can be built in a few steps: the shortest tree, a cheapest pairing of the cities where the tree branches oddly, an Euler circuit, and shortcuts. Nicos Christofides found it in 1976, and for forty-five years nobody could guarantee better. A strip of cities shows the half is really lost, and Laurence Wolsey's reading of the same argument shows it bounds the linear programme too.

part 8 · applied