The Revised Simplex Method

A tableau on a program with 8 constraints and 500 variables updates roughly 4,500 entries per pivot. Most of those columns are never priced, and their updated values are discarded.

The revised method keeps the $8\times 8$ inverse instead, and computes a reduced cost only for a column it actually examines. The algorithm is unchanged, same entering rule, same ratio test, same sequence of bases, but almost none of the arithmetic is the same arithmetic.

What this unit adds is the accounting: which quantities are worth storing, which are cheap to recompute, and what is lost when the state no longer fits on a page.

The order matters: each step uses the previous one's result, and stopping early is possible at two points.

Step 2 is the one that makes the method work. Forming $p$ once converts pricing from a matrix operation into one dot product per column. Recomputing $c_B^{\mathsf{T}}{A}_B^{-1}$ inside the pricing loop gives the same numbers and throws away the entire saving. The most common way to write the method and get no benefit from it.

Two places the iteration stops.

At step 3, if every nonbasic column prices nonnegative, the basis is optimal. Under a first-negative rule pricing halts at the first negative column and the remaining columns are never examined; under a most-negative rule every column is priced before choosing. The first is cheaper per iteration and may take more iterations.

At step 5, if no component of $u$ is positive, no basic variable falls as the entering variable rises: the program is unbounded.

Updating the inverse. The new basis differs in one column, so

where $E$ is the identity with its $l$th column replaced by $(-u_1/u_l,\dots ,1/u_l,\dots ,-u_m/u_l{)}^{\mathsf{T}}$ and $l$ is the leaving row. Applying $E$ is $O(m^2)$; inverting from scratch is $O(m^3)$.

On carrying an explicit inverse. Real implementations do not. They keep an LU factorisation of $A_B$ and solve $A_B^{\mathsf{T}}p=c_B$ and $A_{B}u=A_j$ instead, because repeated updates to an explicit inverse accumulate rounding error. The explicit form is used here because it makes the quantities visible; the algorithm is identical either way.

Start from $B=\{3,4\}$, so $c_B=(0,0{)}^{\mathsf{T}}$ and $A_B=I$.

---

Iteration 1.

Basic values. $A_B^{-1}=I$, so $x_B=b=(24,6{)}^{\mathsf{T}}$; the point is $(0,0,24,6)$ with objective $0$.

Multipliers. $p^{\mathsf{T}}=c_B^{\mathsf{T}}{A}_B^{-1}=(0,0)$.

Pricing. ${\overline{c}}_1=-5-(0,0)\cdot (6,1{)}^{\mathsf{T}}=-5$. Negative, so $x_1$ is eligible. Under a most-negative rule also price ${\overline{c}}_2=-4-0=-4$. Take $x_1$.

Direction. $u=A_B^{-1}{A}_1=(6,1{)}^{\mathsf{T}}$.

Ratio test. Both components positive: $24/6=4$ and $6/1=6$. Minimum $4$ at row 1, so $x_3$ leaves and $\theta =4$.

New basis. $B=\{1,4\}$.

---

Iteration 2.

Inverse. , so

checked by $A_B{A}_B^{-1}=I$.

Basic values. $x_B=A_B^{-1}b=(24/6,-24/6+6{)}^{\mathsf{T}}=(4,2{)}^{\mathsf{T}}$, so $x_1=4$, $x_4=2$, and the point is $(4,0,0,2)$ with objective $-5(4)=-20$.

Multipliers. $c_B=(-5,0{)}^{\mathsf{T}}$, so

Pricing. ${\overline{c}}_2=-4-(-5/6,0)\cdot (4,2{)}^{\mathsf{T}}=-4+20/6=-2/3$. Negative, so $x_2$ enters. (For completeness ${\overline{c}}_3=0-(-5/6,0)\cdot (1,0{)}^{\mathsf{T}}=5/6$, positive.)

Direction. .

Ratio test. $4/(2/3)=6$ and $2/(4/3)=3/2$. Minimum $3/2$ at row 2, so $x_4$ leaves and $\theta =3/2$.

New basis. $B=\{1,2\}$.

---

Iteration 3: the optimality check.

with determinant $8$, so

$x_B=A_B^{-1}b=(24/4-3,-3+4.5{)}^{\mathsf{T}}=(3,3/2{)}^{\mathsf{T}}$.

$c_B=(-5,-4{)}^{\mathsf{T}}$, so $p^{\mathsf{T}}=(-5,-4)A_B^{-1}=(-5/4+1/2,5/2-3)=(-3/4,-1/2)$.

Pricing the two nonbasic columns:

Both nonnegative, so the basis is optimal:

Verification against the original program. $6(3)+4(3/2)=18+6=24$ and $3+2(3/2)=6$, both components nonnegative.

What was never computed. At no point was a full tableau formed. Column 2's direction was computed once, in the iteration that used it; column 3 and column 4 were priced as scalars and never had a direction formed at all. On this four-column problem that saves little; on a program with five hundred columns it is the difference between the method being usable and not.

A note on the fractions. The intermediate quantities are fractional while the data is integral. That is ordinary: nothing about a linear program's data makes its basic solutions integral, which is exactly the property the transportation model has and general programs do not.

The claim is that the new basis inverse is $A_{B^{\prime }}^{-1}=E{A}_B^{-1}$ for an elementary matrix $E$ costing $O(m^2)$ to apply. Here is where $E$ comes from.

Setup. The entering column is $A_j$ with direction $u=A_B^{-1}{A}_j$, and the leaving variable occupies row $l$ of the basis, so by the ratio test.

What changes. The new basis matrix $A_{B^{\prime }}$ equals $A_B$ with its $l$th column replaced by $A_j$. Multiplying on the left by $A_B^{-1}$:

the identity with its $l$th column replaced by $u$, since $A_B^{-1}{A}_B=I$ and $A_B^{-1}{A}_j=u$. Call this matrix $F$.

Inverting $F$. $F$ differs from the identity in one column, and its inverse is the identity with its $l$th column replaced by

the $1/u_l$ sitting in position $l$. This is the matrix $E$. Verifying $FE=I$ is a direct multiplication: column $l$ gives $u\cdot (1/u_l)$ plus the corrections $-u_i/u_l$ from the other columns, which cancel to $e_l$; every other column is unchanged because $E$ agrees with the identity outside column $l$.

The update. From $A_B^{-1}{A}_{B^{\prime }}=F$,

The cost. $E$ differs from the identity in one column, so forming $E{A}_B^{-1}$ means scaling row $l$ of $A_B^{-1}$ by $1/u_l$ and adding a multiple of it to each other row: $O(m^2)$ arithmetic, against $O(m^3)$ to invert $A_{B^{\prime }}$ directly.

Why this is exactly a tableau pivot. The operations just described, scale the pivot row, subtract multiples from the others, are the row operations a tableau performs. The difference is scope: the tableau applies them to all $n+1$ columns, the revised method to the $m$ columns of the inverse. Same operations, different object.

Why implementations stop here. Each iteration multiplies by another $E$, so after $k$ iterations the inverse is a product of $k$ elementary matrices applied to the original. Rounding error compounds along that product. Implementations therefore store the $E$ factors (the product form of the inverse) or an LU factorisation, and refactorise from scratch periodically. The mathematics above is what they are approximating.

Take the program from the tableau unit: $min-3x_1-2x_2$ subject to $x_1+x_2+x_3=4$, $x_1+3x_2+x_4=6$, from $B=\{3,4\}$.

Same entering variable, same leaving variable, same step, same optimum. The reduced costs the tableau displays in its bottom row, $(0,1,3,0)$, are the numbers the revised method computes as $c_j-p^{\mathsf{T}}{A}_j$ when it prices. They are the same quantities, obtained differently.

Where they diverge in cost. With $m=2$ and $n=4$ the tableau updates 15 entries per pivot and the revised method updates 4. At $m=8$, $n=500$ the tableau updates about 4,500 and the revised method 64, plus one dot product per column actually priced.

Where they diverge in what you can see. Reading optimality off a tableau is one glance. In the revised method it is a conclusion drawn after pricing, with nothing to look at. Conversely, asking why ${\overline{c}}_2=1$ has an answer in the revised form, it is $c_2-p^{\mathsf{T}}{A}_2$, and $p$ came from $c_B^{\mathsf{T}}{A}_B^{-1}$, where in the tableau the entry is the result of accumulated row operations with no derivation attached.

Which to use when. By hand on a small program, the tableau: the state is visible and the arithmetic is mechanical. In an implementation, or on any program with many more columns than rows, the revised form. For understanding what a solver reports, the revised form again, because its quantities are the ones a solver's log and sensitivity output actually name.