Why Real Solvers Use Revised Simplex

Examines the computational reasons that production LP solvers implement the revised simplex method instead of the explicit tableau: smaller working memory, preservation of sparsity in the constraint matrix, and lower per-iteration flop counts. Students compute concrete memory and arithmetic comparisons for realistically-sized LPs.

Step 1 of 157%

Tutorial

Working Memory: Tableau vs. Basis Inverse

Real linear programs typically have $n \gg m$ — many more variables than constraints. A logistics LP might have $m = 500$ constraints but $n = 50{,}000$ decision variables. Working memory becomes a first-order concern.

The explicit simplex tableau maintains every entry of an $m \times (n+1)$ array of numbers across every iteration: $m(n+1)$ stored entries.

The revised simplex method maintains only:

the basis inverse $B^{-1}$ (or, equivalently, its $LU$ factorization), an $m \times m$ object — $m^2$ stored entries;
read-only access to the original problem data $A,\ \mathbf{b},\ \mathbf{c}$ (which both methods need to load anyway).

The relevant comparison is

\underbrace{m(n+1)}_{\text{tableau}} \quad \text{vs.}\quad \underbrace{m^2}_{\text{basis inverse}}.

Notice that $m^2$ does not depend on $n.$ When $n \gg m,$ the tableau is approximately $n/m$ times larger than the basis inverse.

Illustration: $m = 30,\ n = 600.$

Tableau: $30 \cdot 601 = 18{,}030$ entries.
Basis inverse: $30^2 = 900$ entries.
Ratio: $18{,}030 / 900 \approx 20.$

For industrial-scale LPs with $n/m \approx 100,$ the tableau is roughly $100\times$ the basis inverse — often the difference between fitting in fast memory and not.