Prices at every corner

Every figure on duality so far has found a linear program’s optimum the same way: form every pair of constraints, solve each pair for the point where they cross, throw away the crossings that break some other constraint, and compare what is left. With two variables and five constraints that is twenty-one small calculations and it is a perfectly good method. With twenty variables and fifty constraints it is one calculation for every way of choosing twenty constraints out of fifty — about forty-seven trillion of them — and it is not.

The duality theorem does not help directly. It says that the best value of a program equals the best value of its dual, and that equality is a statement about two optima, not a recipe for finding either. What turns it into a recipe is a small observation about a single corner, and George Dantzig built the method on it in 1947, the same year the dual was first written down.

The figure below is that method at work. A polygon with seven corners, a walk that starts at the origin and moves along the edges from corner to corner, and a table that records, at each corner, two numbers the walk uses to decide where to go next. After three moves the two numbers are both non-negative, and the walk stops — not because it has run out of ideas, but because it holds a proof.

Two constraints, and the objective split between them #

At a corner of a two-variable program, two constraints hold with equality. Each has an outward direction — the direction in which moving would break it — and the objective, the direction in which the value climbs, can be written as a combination of those two outward directions:

$$c \;=\; \mu_1 r_1 + \mu_2 r_2.$$

Two directions in the plane that are not parallel can combine to give any third, so the two numbers $\mu_1$ and $\mu_2$ always exist and are unique. They are the prices of the two constraints at that corner. The name is exact, and what a constraint is worth is the essay that earned it: loosen the first constraint by a small amount, keep the second tight, and the best value reachable from this corner changes by $\mu_1$ per unit.

Now suppose both prices are non-negative. Then the corner is optimal, and the reason is weak duality in two lines. For any feasible point $x$ and the corner $z$,

$$c \cdot x = \mu_1 (r_1 \cdot x) + \mu_2 (r_2 \cdot x) \;\le\; \mu_1 b_1 + \mu_2 b_2 = c \cdot z,$$

because each $r_i \cdot x$ is at most $b_i$ and the multipliers are not negative. No feasible point beats the corner. The prices are a dual solution, and their value equals the corner’s value, so the two numbers of the duality theorem have met, here, at this corner.

A negative price names an edge #

If one of the prices is negative, the argument fails — and it fails usefully.

A negative price on the first constraint says the objective would improve if that constraint were tightened, which is the same as saying it improves if the point moves away from that constraint’s line. And moving away from one line while keeping the other tight is exactly moving along the other constraint’s edge. So a negative price is not merely a failed certificate; it names a direction. The objective points outside the wedge of the two outward directions, and some edge leaving the corner climbs.

Geometrically that is the whole method. Inside the wedge, stop; outside it, leave along the edge the negative price points to. Follow that edge until another constraint gets in the way — the first one hit is found by comparing, for each constraint not yet tight, how far the edge can go before breaking it — and the new corner is where the two constraints now meet.

The walk, corner by corner #

The hero’s program is to maximise $2x_1 + 3x_2$ over a polygon cut out by five constraints and the two axes. The walk starts at the origin, where the two tight constraints are the axes themselves.

At the origin both prices are negative: $-2$ and $-3$. Both edges climb. Dantzig’s rule takes the more negative price, $-3$, which leaves the axis $x_2 \ge 0$ and moves up the $x_1 = 0$ edge; it stops at $(0, 8)$, where the constraint $x_2 \le 8$ gets in the way. The value there is $24$.

At $(0, 8)$ the prices are $-2$ on the axis and $3$ on row 5. One negative price; the walk leaves the axis and moves along $x_2 = 8$ to $(1, 8)$, value $26$. There the prices are $-3$ on row 5 and $2$ on row 4, so the walk leaves row 5 and moves along row 4 to $(\tfrac52, \tfrac{15}2)$, value $\tfrac{55}2$. And there the prices are $\tfrac12$ on row 4 and $\tfrac32$ on row 3. Neither is negative. The walk stops.

Three moves, four corners visited out of seven, and the answer is not merely found but proved. At no point did the walk look at a corner it did not step on.

The certificate the walk ends with #

The final prices are worth reading as what the duality theorem calls them: a solution of the dual program.

The dual solution is $(0, 0, \tfrac32, \tfrac12, 0)$ — a price on each of the five constraints, nought on the three that are slack at the optimum and the walk’s two final prices on the two that are tight. Its value is $10 \cdot \tfrac32 + 25 \cdot \tfrac12 = \tfrac{55}2$, the same as the primal. Every constraint either has no slack or has no price, which is complementary slackness, and it holds here not as a theorem checked afterwards but as something the walk maintained at every step: it only ever put prices on constraints that were tight.

The prices also answer a question the walk never asked. Loosen $x_1 + x_2 \le 10$ to $x_1 + x_2 \le 11$ and the best value rises by $\tfrac32$; loosen $x_1 + 3x_2 \le 25$ by one and it rises by $\tfrac12$; loosen any of the other three and nothing happens, because the optimum is not touching them. Those are the rates the optimum’s graph has as its resources change, and a planner who has just solved the program also knows, at no extra cost, which resource to buy more of and what it is worth — until the walk’s final pair of constraints stops being the right pair, at which point the rates jump and a new walk, starting from the old corner, finds the new ones in a move or two.

So the simplex method is best described not as a search for the primal optimum but as a search for a pair — a corner and a set of prices — satisfying three conditions. The corner is feasible, which the walk keeps true at every step. The prices are only on tight constraints, which it also keeps true. And the prices are non-negative, which is the one condition it does not have until the end. Every move is an attempt to repair the last condition without breaking the first two.

The first program, walked #

Two numbers that have to meet began with a smaller program: maximise $3x_1 + 4x_2$ subject to $3x_1 + 2x_2 \le 12$ and $x_1 + 4x_2 \le 10$. Its optimum was found by trying every pair of constraints, and the dual optimum separately by the same exhaustion on the dual region.

The walk takes two moves: up the $x_2$-axis to $(0, \tfrac52)$, where $x_1 + 4x_2 \le 10$ stops it, and along that constraint to $(\tfrac{14}5, \tfrac95)$. The prices there are $\tfrac45$ and $\tfrac35$ — exactly the dual optimum found when duality was first met, and exactly the slopes the optimum’s graph had on the stretch where both constraints bind. Three computations done separately before — the primal optimum, the dual optimum, and the rate at which the optimum responds to its resources — were one computation all along, and the walk is it.

Which negative price to follow #

When both prices are negative, both edges climb, and the method has to choose. Dantzig’s rule takes the more negative one, on the reasonable ground that it climbs fastest. It is a rule of thumb, not a theorem, and the choice matters.

On a polygon there are only two routes from the origin, clockwise and anticlockwise, and every rule picks one of them. On this polygon the steep start happens also to be the short way round. That is luck, and the cube that takes every corner shows what the luck can cost: a program in three variables arranged so that the steepest edge is always the long way round, and the walk visits every corner there is.

Other rules exist. The steepest edge rule measures the climb per unit of distance travelled rather than per unit of the variable changed, which is more expensive per step and usually needs far fewer steps. Robert Bland’s rule, from 1977, takes the negative price on the constraint with the lowest number, which looks arbitrary and has one virtue no other simple rule has: it can never go round in a circle, for a reason the next section explains.

Three constraints through one corner #

A corner is supposed to be where two constraints meet. Sometimes three meet there, and then the prices at that corner are no longer unique.

The corner $(3, 7)$ is optimal for $x_1 + 2x_2$, and three constraints pass through it. Pairing the first two gives prices $\tfrac12$ and $\tfrac12$ — a certificate. Pairing the first and third gives $1$ and $1$ — another certificate, a different dual optimum, which is possible because the dual has more than one. Pairing the second and third gives $1$ and $-1$, and a walk that arrived holding that pair would see a negative price and try to leave along an edge that does not climb at all: the edge’s length before it hits the third constraint is nought. The method then swaps one constraint in the pair for another without moving, and tries again.

Such stationary moves are called degenerate pivots, and in two dimensions they do no harm. In higher dimensions they can: Alan Hoffman in 1953 and E. M. L. Beale in 1955 built programs on which a walk following Dantzig’s rule swaps constraints at one degenerate corner forever, returning to a set of prices it has already held. Bland’s lowest-number rule provably never repeats a set, and a small random perturbation of the right-hand side makes every corner an ordinary one; both are used in practice.

Why a walk beats a search #

The enumeration used before looks at every corner. The walk looks at the corners on one path. The difference is the difference between a method and a theorem.

A program with $n$ variables and $m$ constraints can have a number of corners that grows like $m^{n/2}$, and each step of the walk touches only one of them and its $n$ neighbours. In practice — measured by Dantzig and everybody since, on programs from shipping schedules to diets to the design of oil refineries — the walk reaches the optimum in a number of moves comparable to the number of constraints, typically between one and three times $m$. That is why the simplex method, and not enumeration, is what linear programming means in practice, and why it was named in 2000 as one of the ten algorithms of the century.

The same walk, with the same prices, appears elsewhere under other names. The auction that sells houses raises prices until nobody wants to switch, which is a walk in the space of prices rather than of corners. The Hungarian method for assignment adjusts a price on every person and task until the prices certify a matching. Each is the idea of this essay — keep a partial answer and a set of prices consistent with it, and move until the prices prove the answer — specialised to one shape of program.

When the edge never ends, and when there is no corner to start from #

Two things can go wrong with the walk as described, and each of them turns out to be one of the cases the duality theorem has to allow for.

The first is an edge that climbs for ever. A negative price names an edge, and the walk follows it until some constraint gets in the way — but if no constraint lies across that edge, the step length has no limit, the objective increases without bound along it, and the program has no optimum at all. The walk does not need to be told this separately. The comparison that finds the next corner comes back empty, and the edge it was about to follow is itself the proof: a direction in which every point is feasible and the value keeps rising. That is the unbounded case, detected at exactly the step where it matters.

The second is a program whose origin is not feasible, so the walk has nowhere to start. The standard repair is to walk a different program first — one that measures how badly each constraint is broken and minimises the total — whose origin is feasible by construction. If that auxiliary walk reaches a total of nought, it has found a corner of the real program and the real walk begins there. If it cannot get below some positive amount, the prices it ends with are again a certificate, but a certificate of a different kind: a weighted sum of the constraints that is impossible to satisfy, which is Farkas’s lemma, the wall between two bodies specialised to half-planes. The program is infeasible, and the walk says why.

So the three outcomes of a linear program — an optimum, no bound, no feasible point — are the three ways a walk can end, and each ends with a certificate. The optimum comes with prices; the runaway comes with a direction; the empty program comes with an impossible combination. Nothing is ever reported without the evidence for it.

Games, assignments, and corners that come out whole #

Because the walk ends with prices, anything that can be written as a linear program inherits both an algorithm and a certificate, and several subjects turn out to be linear programs in disguise.

A two-player game where one side’s gain is the other’s loss has a value, and each player has a mixed strategy guaranteeing it. Finding the strategies is a linear program, and its dual is the other player’s program: the walk that finds one player’s best mixture ends holding the other player’s as its prices. Von Neumann’s minimax theorem and the duality theorem are the same statement, which is why he recognised Dantzig’s dual on sight.

An assignment of people to tasks is a linear program whose corners are all whole assignments. The walk only ever stands on corners, so it can only ever stand on a whole assignment: solved as a linear program, the assignment problem never returns a fractional answer, even though nothing in the method asked for whole numbers. The integrality is a property of the polytope, and the walk simply cannot leave the corners where it lives.

What a polygon cannot show #

A polygon has two edges at every corner, so the walk’s only decision is which way round to go. In $n$ variables a corner has $n$ edges, the prices are $n$ numbers, and the rule is choosing among up to $n$ negative ones; the figures can show none of that choice except its two-way shadow.

Nor can a polygon show the tableau, the bookkeeping that lets the method work in many dimensions without ever drawing a corner. Each step is one exchange in a table of coefficients — a row operation that swaps one tight constraint for another — and the prices are read off one row of the table. The figures compute every price directly from the two tight constraints, which is the same arithmetic done in a form that only works in the plane.

And the count of moves on a polygon says nothing about the count in general. Three moves out of seven corners, or four, is not evidence about how long the walk takes on a program with a million corners. That is the subject of the Klee–Minty cube, and the answer is not comfortable.

Still open: a rule that is always fast #

In practice the walk is fast. In the worst case, for every pivot rule anyone has analysed carefully — Dantzig’s, Bland’s, steepest edge, and many others — there are programs on which it takes a number of moves exponential in the number of variables. Whether some pivot rule takes only polynomially many moves on every program is not known.

The question is tied to a geometric one that is also open: how many edges separate the two furthest corners of a polytope, in the worst case, as a function of its dimension and number of faces? If that distance can be exponential, no rule can be fast, since the walk moves along edges. The best known upper bound, due to Gil Kalai and Daniel Kleitman in 1992, grows faster than any polynomial; no polytope is known whose distances are more than a modest multiple of the number of its faces. The gap between those two statements is where a fast rule, or a proof that none exists, would have to live.