Finiteness is not efficiency. A smallest-index rule proves the method stops; a deformed n-dimensional cube makes the most-negative rule visit all 2ⁿ of its corners, taking exactly 2ⁿ - 1 pivots; and ordinary problems finish in a small multiple of the number of rows. Those three statements are each true, none implies another, and saying all three is the honest status of the algorithm.
Core ideas
The hard idea is a negative one: three facts about the method are independent, and almost every confident sentence about simplex speed is one of them being used to imply another.
There are finitely many bases and a smallest-index rule never repeats one, so the run ends. That argument says nothing whatever about how many of those bases get visited, and the number available grows combinatorially. “It stops” and “it stops soon” are different claims and only the first has been proved.
A deformed cube can be built whose 2ⁿ vertices the most-negative rule visits every one of, costing 2ⁿ - 1 pivots: 3, 7, 15 at n = 2, 3, 4. The coefficients run from 1 to 10ⁿ⁻¹ and the comparisons that pick the entering column have to land exactly. Round one of them the other way and the count collapses, taking the example with it.
Keep the same cube and the same optimal vertex, turn the objective coefficients round, and the most-negative rule walks straight there in one pivot. The smallest-index rule takes exactly what it took before, because it never reads a coefficient. Same region, same answer, counts from 1 to 15.
The material
The cube, the counts under four rules, the two false implications this lesson exists to separate, and the sentence that is actually true.
“Degeneracy, Cycling and Bland’s Rule” closed with a guarantee: with the smallest-index rule the method reaches an optimal basis or a certificate of unboundedness in finitely many pivots. That guarantee is a counting argument over the set of bases, and the set of bases is large: n choose m, which for a hundred rows and two hundred columns is a number with more than fifty digits. Finiteness on its own promises nothing useful.
For n ≥ 2, the programme maximise Σ 10ⁿ⁻ʲ x_j subject to 2 Σ_{j < i} 10ⁱ⁻ʲ x_j + x_i ≤ 100ⁱ⁻¹ for i = 1, …, n, with x ≥ 0. Its feasible region is a deformed n-cube with 2ⁿ vertices, its optimum is 100ⁿ⁻¹, and the most-negative entering rule starting from the origin visits every vertex, taking 2ⁿ - 1 pivots.
At n = 3 that is maximise 100x₁ + 10x₂ + x₃ subject to x₁ ≤ 1, 20x₁ + x₂ ≤ 100 and 200x₁ + 20x₂ + x₃ ≤ 10000. Eight vertices, seven pivots, optimum 10000 at (0, 0, 10000) — which the method reaches by walking through all eight.
The doubling is the whole point, and it is already plain at 15. At n = 5 the count is 31 against 15, and there is no new information in watching it, which is why the lab’s dimension control stops at four.
Keep the region exactly as it is and reverse the objective coefficients — 1, 10, 100 instead of 100, 10, 1. The optimal vertex does not move. The most-negative rule now takes one pivot at every n. The smallest-index rule takes 3, 5, 9 as before, unchanged, because it never looks at a coefficient at all.
So 2ⁿ - 1 is not a fact about cubes and not a fact about the simplex method. It is a fact about one rule on one objective over one region, and the construction is exactly the work of arranging all three to be adversarial together. That is what “worst case” means, and it is why worst cases have to be built rather than found.
The first is “the simplex method is exponential, so it is slow”. The premise is about a worst case over all inputs and the conclusion is about the inputs anyone actually has. Observed pivot counts on real problems run at a small multiple of the number of rows, which is why the method was in production use for decades before anyone knew whether linear programming was tractable at all.
The second is its mirror: “linear programming is polynomial, so the simplex method is”. Linear programming is solvable in polynomial time — the ellipsoid method established it and interior-point methods made it practical — and those are different algorithms. A problem being in a complexity class says nothing about a particular algorithm for it, any more than sorting being possible in n log n time makes bubble sort fast.
The words in both sentences are borrowed: “worst case”, “polynomial” and “input size” are defined in “P, NP and NP-Completeness” on the Discrete Mathematics path. That is a citation rather than a prerequisite — nothing on this course needs anything else from there, and a reader who has not taken it loses only the formal definitions of three phrases used here in their ordinary sense.
Three statements, each true, none implying another. The method is finite, because under a smallest-index rule no basis repeats and there are finitely many. It is exponential in the worst case, because this cube exists and the count on it is exactly 2ⁿ - 1. It is fast in practice, because problems like this cube are constructed rather than met. Reporting all three is the honest status of the algorithm, and dropping any one of them produces a sentence that is wrong in a direction someone will act on.
One last thing this course has to say about its own arithmetic. Neither of the two famous results is reproducible in floating point at all. The cycling example returns to its starting tableau entry for entry only if nothing has been rounded, and the count 2ⁿ - 1 holds only if the comparisons among coefficients from 1 to 10ⁿ⁻¹ land exactly. Every figure on these nine pages is an exact fraction, and in these two lessons that is the content rather than the style.
Interactive
Finite is not fast: the pivot count measured against two to the n minus one, under four rules
Method
Four questions, asked separately. Most wrong statements about simplex speed come from answering one of them and reporting the answer as another.
The smallest-index rule terminates on every programme; the most-negative rule can cycle. That is a yes-or-no question about the rule, answered by a counting argument, and it has no numbers in it.
“Exponential” here means: there is a family of programmes on which this rule takes 2ⁿ - 1 pivots. Name the family, because a worst case with no construction attached is a rumour, and the construction is what shows the objective is doing as much work as the region.
Run the method and count. Observed counts on ordinary models are a small multiple of the number of rows, which is a measurement rather than a theorem, and it is the number that decides whether the method is usable.
Linear programming is solvable in polynomial time by other methods. That is a statement about the problem, it does not transfer to the simplex method, and the reverse transfer — from the simplex worst case to the difficulty of linear programming — fails as well.
They are all true. Finite, exponential in the worst case, fast in practice: a summary that keeps only the first is useless, only the second is alarmist, and only the third is unjustified.
Eight vertices and every one of them visited. The same region and the same optimal vertex are then solved in a single pivot by turning the objective coefficients round, which is the clearest statement of what the count actually depends on.
Read the reversal carefully, because it is the whole lesson in two lines. The constraints did not change. The optimal vertex did not change — (0, 0, 10000) both times. Only the objective coefficients were turned round, and the most-negative rule went from seven pivots to one, while the smallest-index rule took exactly what it took before because it never reads a coefficient. 2ⁿ - 1 is a property of a rule and an objective together, not of a shape.
None of these counts survives rounding. The coefficients at n = 4 run from 1 to 1000, the right-hand sides to 1000000, and the comparisons that choose the entering column have to land exactly; in floating point one of them lands the other way, the count collapses, and the example goes with it. That is why the cube is here rather than in a footnote — it can only be shown on a page whose arithmetic is exact.
For a faded rehearsal, set the lab to n = 4 and work through the three questions separately before looking at the panel. The supplied first move is the bound: 2⁴ - 1 = 15. Predict the most-negative count, then the smallest-index count, then the greatest-improvement count; then reverse the objective and predict all three again. Finally write one sentence about the speed of the simplex method that would still be true if all six predictions were wrong.
You should be able to state the termination argument and what it does not deliver, run the cube at two dimensions and count the pivots against 2ⁿ - 1, change the rule and the objective and explain the new counts, separate the two false implications about polynomial time, and say why neither famous result is reproducible in floating point.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.