The cube that takes every corner

The simplex method walks from corner to corner of a linear program’s feasible region, each time following an edge that a negative price says will climb, until the prices at a corner are all non-negative and prove it optimal. On the programs people actually solve it needs a number of moves comparable to the number of constraints, and for twenty-five years after Dantzig proposed it nobody knew whether that was a law or a habit.

There were good reasons to hope it was a law. The duality theorem guarantees that the walk’s destination exists and that it will recognise it on arrival; every move strictly improves the objective, so no corner is visited twice unless the walk stalls at a degenerate one; and the number of corners, although enormous, is finite. What none of that bounds is the length of the path. A walk that improves at every step can still be forced to take a very long way round, if the region is shaped so that every improving step is a small one.

Victor Klee and George Minty settled it in 1972, and not in the method’s favour. They wrote down, for every $n$, a program in $n$ variables whose feasible region is a squashed $n$-dimensional cube, and showed that the simplex method with Dantzig’s rule — always leave by the most negative price, which is to say along the steepest edge — visits every one of its $2^n$ corners before stopping.

The figure below is the three-dimensional case, drawn twice: on the left the program’s own region, each axis scaled to fit, and on the right the plain cube it is a squashed copy of. The numbers are the order of the walk, nought to seven. Every corner is visited, the objective rises at every move, and the dashed edge — which the walk never takes — goes from the first corner directly to the last.

A square that sends the walk the long way #

The construction starts in two dimensions, where there is only one way to be inefficient: go round the long side.

The program is to maximise $2x_1 + x_2$ with $x_1 \le 1$ and $4x_1 + x_2 \le 5$. At the origin both prices are negative, $-2$ for $x_1$ and $-1$ for $x_2$, and the rule leaves by the steeper: along the $x_1$-axis to $(1, 0)$, worth $2$. Then up to $(1, 1)$, worth $3$. Then along the slanted constraint to $(0, 5)$, worth $5$, where the walk stops. The optimum was one move from the origin, up the $x_2$-axis, along the edge the rule rejected because it climbed only half as fast.

The trick is in the slant. The constraint $4x_1 + x_2 \le 5$ lets $x_2$ grow to $5$ only when $x_1$ is nought, and to only $1$ when $x_1$ is one. The steep direction is a trap, because taking it uses up the room the shallow direction needed. That is the whole idea, and everything else is doing it again one dimension up.

Stacking the square into a cube #

Add a third variable, weighted in the objective half as much as the second, and a third constraint that lets it grow to $25$ only when the first two are nought:

$$\begin{aligned} &\max\; 4x_1 + 2x_2 + x_3 \\ &\text{subject to}\;\; x_1 \le 1, \\ &\phantom{\text{subject to}\;\;} 4x_1 + x_2 \le 5, \\ &\phantom{\text{subject to}\;\;} 8x_1 + 4x_2 + x_3 \le 25. \end{aligned}$$

On the floor, where $x_3 = 0$, the program is the square again, and the walk does exactly what it did there: three moves to $(0, 5, 0)$, the far corner of the floor. Only then does $x_3$ have the steepest price, and the walk climbs up one edge to the ceiling, at $(0, 5, 5)$.

The ceiling is where the construction earns its keep. The third constraint slopes, so on the ceiling $x_3$ is larger wherever $x_1$ and $x_2$ are smaller — and the objective, which weights $x_3$ least, is nevertheless arranged so that on the ceiling the walk is drawn back across the square in reverse, from $(0, 5)$ to $(1, 1)$ to $(1, 0)$ to $(0, 0)$, gaining a little at every move because $x_3$ grows as the others shrink. Four corners on the floor, four on the ceiling, seven moves, and the optimum $(0, 0, 25)$ sits directly above the start.

In $n$ variables the same stacking is done $n - 1$ times: $\max \sum_j 2^{n-j} x_j$ subject to $\sum_{j<i} 2^{i-j+1} x_j + x_i \le 5^{i-1}$. Each new variable doubles the number of corners and the walk visits the whole of the previous cube, climbs one edge, and visits the whole of it again backwards. So the number of moves obeys $M(n) = 2M(n-1) + 1$, which is $2^n - 1$. The figures compute that count by running the walk, at every $n$ from two to ten, and it is exactly $2^n - 1$ every time.

The order of the corners is a Gray code #

Label each corner by which of the $n$ sloping constraints it lies on — a string of $n$ bits, one for on and nought for off. The walk moves along edges of a cube, and an edge of a cube changes exactly one coordinate, so consecutive corners differ in exactly one bit.

The list of face patterns is 0000, 1000, 1100, 0100, 0110, 1110, 1010, 0010, 0011, … — the reflected binary Gray code, the order through all the words of $n$ bits in which each step changes one bit, written with its first bit on the left. The reflection that builds the Gray code (list the Gray code for $n - 1$ bits, then the same list backwards with a new bit set) is exactly the stacking that builds the walk. The figure checks the correspondence at every one of the sixteen rows rather than taking it on trust.

That is a surprising place for a Gray code to turn up. Nobody designing a counter or a rotary encoder was thinking about linear programs, and nobody designing a program to defeat the simplex method set out to produce one. The Gray code is simply what a longest possible walk on a cube looks like when every step must be an improvement: a Hamiltonian path, the walk that visits every corner once, whose values happen to be increasing.

Steep edges that are short #

Why does the walk not escape? At every corner it has a choice among up to $n$ edges, and it always takes the steepest. The cube is arranged so that the steepest edge is always a short one.

At the origin the four edges climb at rates $8$, $4$, $2$ and $1$ — the objective coefficients $2^{n-j}$. The steepest edge ends after one unit, gaining $8$. The shallowest ends after $125$ units, gaining $125$, which is the whole answer. Dantzig’s rule measures how fast an edge climbs, not how far, and the program’s coefficients are chosen so that the two are in opposite order: each new variable’s constraint has five times the room of the last and half the weight in the objective. The factors are not magic — any ratio large enough to keep every move an improvement will do — but a ratio between steepness and length is the mechanism, and it is visible in the bars.

A rule that measured the gain of a whole move rather than its rate would not be fooled by this particular cube. It is fooled by another. Robert Jeroslow built one in 1973 for the greatest-improvement rule; Donald Goldfarb and William Sit built one in 1979 for the steepest-edge rule, which measures climb per unit of distance travelled. Every deterministic pivot rule that has been analysed has its own squashed cube.

Exponential on paper, a handful in practice #

The cube makes the worst case exponential. What it does not change is the typical case, and the gap between the two is the most striking thing about the method.

At $n = 10$ the walk on the cube takes $1{,}023$ moves. On random programs of the same size — ten variables, ten constraints with random positive coefficients, forty of them averaged — it takes about five. The cube is not a hard program; its optimum is one edge away. It is a program designed against one specific rule, and the rule falls for it exactly.

The figure also runs Bland’s rule, the one that never cycles. On these cubes it does better — $177$ moves at $n = 10$ — and its counts follow a pattern worth noticing: $3, 5, 9, 15, 25, 41, 67, 109, 177$, each the sum of the two before it plus one. That is the Fibonacci recurrence, so the counts grow like the golden ratio to the power $n$: slower than doubling and still exponential. Bland’s rule is not fooled by this cube the way Dantzig’s is, and is fooled by others; Avis and Chvátal showed in 1978 that it too can be driven through exponentially many corners.

A cube shaken out of shape #

If the worst case needs such a precise arrangement, a small random disturbance should destroy it.

It does. Spreading each coefficient by ten per cent cuts the thousand moves at $n = 10$ to about 380; thirty per cent cuts it to about seventy-five. The long walk depended on the fives and twos being exactly what they are, so that every steep edge is short and every move lands exactly on the corner the next move needs.

This is the idea that finally explained the method’s practical speed. Karl-Heinz Borgwardt proved in 1982 that for one pivot rule, the shadow-vertex rule, the average number of moves on programs drawn from a natural random distribution grows only polynomially. Daniel Spielman and Shang-Hua Teng proved in 2001 something much stronger and more relevant: take any program, disturb its coefficients by a small random amount, and the shadow-vertex rule’s expected number of moves on the disturbed program is polynomial in the size and in the inverse of the disturbance. Worst cases exist, but they are isolated points, and the neighbourhood of every program is easy. They called it smoothed analysis, and it won the Gödel Prize in 2008.

The figure here uses Dantzig’s rule and a multiplicative disturbance, which is not the setting of either theorem. It shows the phenomenon, not the proof.

How far the optimum could be #

The cube’s optimum is one edge from the start, so the walk’s length says nothing about how far apart corners can be. That is a separate question, and it is the one that decides whether any rule at all could be fast: however clever the rule, the walk moves one edge at a time, so it can never take fewer moves than the number of edges between the start and the optimum.

In 1957 Warren Hirsch conjectured that the answer was small. For a region in $d$ dimensions bounded by $m$ flat faces, any two corners should be joined by a path of at most $m - d$ edges. For a cube, with $2d$ faces, that says $d$ — and the cube’s two furthest corners, opposite each other, are exactly $d$ edges apart, one coordinate changed at a time. The conjecture held up for more than fifty years and was checked in many families.

In 2010 Francisco Santos found a counterexample: a region in 43 dimensions with 86 faces, in which two corners are at least 44 edges apart, one more than the conjecture allows. It was the first counterexample, and it exceeds the bound by only a few per cent, which leaves the question that matters wide open. Nobody knows whether the distance between corners is always bounded by a polynomial in $m$ and $d$ — the polynomial Hirsch conjecture — and the best upper bound, Kalai and Kleitman’s of 1992, grows faster than any polynomial.

Exact answers exist for special regions, and they can be startlingly hard. The corners of the associahedron are the triangulations of a polygon and its edges are single flips, and the largest number of flips needed between two triangulations of an $n$-gon is $2n - 10$ for all large $n$ — a fact whose first proof, in 1988, went through hyperbolic geometry in three dimensions. That is one family of regions. The general question is about all of them.

Rules that toss a coin #

A deterministic rule can be anticipated: a program can be built to exploit whatever it will do next. A rule that chooses at random among the climbing edges cannot be anticipated in the same way, and for a while that looked like the escape.

Two random rules have been studied closely. Random-edge chooses uniformly among the edges that climb. Random-facet, proposed independently by Gil Kalai and by Jiří Matoušek, Micha Sharir and Emo Welzl in 1992, chooses a random face of the region and solves the problem on it recursively; its expected number of moves is subexponential — smaller than any $c^n$ — which is the best proved bound for any version of the simplex method. In 2011 Oliver Friedmann, Thomas Hansen and Uri Zwick showed that both rules can nevertheless be forced to take a subexponential but superpolynomial number of moves, using programs built from a game rather than from a cube: the prices at the corners mimic the strategy updates of a two-player game on a graph that takes a very long time to settle.

The same year Friedmann disposed of a rule Norman Zadeh had proposed in 1980 with a prize of a thousand dollars for anyone who could defeat it: leave by the edge that has been used least often so far. Friedmann built programs on which it too takes superpolynomially many moves, and collected the prize. Each new rule has so far found its own cube.

Polynomial after all, off the corners #

The cube proved that walking corners cannot be guaranteed fast. It did not prove that linear programming is hard, and it is not.

In 1979 Leonid Khachiyan showed that the ellipsoid method — a way of shrinking an ellipsoid around the feasible region, cutting its volume by a fixed factor at each step — solves linear programs in time polynomial in the number of digits needed to write them down. It was the first proof that deciding which of the four outcomes a program has is a polynomial problem, and it was far too slow to use. In 1984 Narendra Karmarkar gave an interior-point method, which travels through the middle of the region toward the optimum instead of along its edges, and it was both polynomial and fast; its descendants now compete with the simplex method on large programs and win on many.

Neither method walks from corner to corner, and that is the point. The squashed cube is a trap for walks along edges. A method that cuts through the middle of the region never meets its $2^n$ corners at all.

What the pictures cannot settle #

The walk counts in the figures are exact: the program is run, every corner is checked against every constraint, and the count is compared with $2^n - 1$ at every size. But they go up to ten variables, and a claim about all $n$ is a claim about infinitely many cubes. The recurrence $M(n) = 2M(n-1) + 1$ is what carries the count to every size, and it rests on the reflection argument, which the figures illustrate at three and four dimensions and do not prove.

The random programs are forty samples from one distribution, chosen for convenience. A different distribution — sparse coefficients, many more constraints than variables, the structure of a real scheduling problem — would give different counts, and the claim that “typical” programs are easy is a statement about programs people meet, which no sample can define.

And the drawings of the cube are drawings of three dimensions. The four-dimensional walk appears only as a table, and the ten-dimensional one only as a count.

Still open: a method that counts only operations #

Khachiyan’s and Karmarkar’s methods are polynomial in the number of digits of the coefficients: double the precision of the data and the running time goes up. For many problems — shortest paths, network flows, the cheapest way to send them, matchings — there are methods whose number of arithmetic operations depends only on the number of variables and constraints, not on the size of the numbers. Every one of those problems is a linear program, and every one of them has a structure that a general program lacks. They are called strongly polynomial.

Whether linear programming has a strongly polynomial algorithm is not known. Stephen Smale listed it in 1998 as the ninth of his problems for the twenty-first century. A simplex method with a pivot rule that was polynomial on every program would be one; so would an interior-point method whose number of steps did not depend on the data’s precision. Neither is known, and the Klee–Minty cube, which disposed of the simplest hope in 1972, remains the reason nobody assumes the answer.