The Revised Simplex Method

The same algorithm organised around the basis inverse rather than a full table. Multipliers are formed once per iteration, columns are priced only as they are examined, and the single direction needed for the ratio test is computed on demand. What changes is what gets stored and recomputed, not which basis sequence the method visits.

Definition

The revised simplex method carries the basis inverse $A_{B}^{- 1}$ and the current basic values, and computes everything else when it is needed. One iteration from basis $B$ :

Basic values. $x_{B} = A_{B}^{- 1} b$ , with all nonbasic variables at zero.
Multipliers. $p^{T} = c_{B}^{T} A_{B}^{- 1}$ , formed once, as a single row vector.
Pricing. For nonbasic $j$ , ${\bar{c}}_{j} = c_{j} - p^{T} A_{j}$ , computed column by column. Stop at the first ${\bar{c}}_{j} < 0$ under a first-negative rule, or price every column to apply a most-negative rule. If all are nonnegative, the basis is optimal.
Direction. For the entering column alone, $u = A_{B}^{- 1} A_{j}$ .
Ratio test. $θ = min {x_{B (i)} / u_{i} : u_{i} > 0}$ . If no $u_{i} > 0$ , the program is unbounded.
Update. The row attaining the minimum leaves; $x_{j}$ enters at $θ$ ; the remaining basic values become $x_{B (i)} - θ u_{i}$ ; and $A_{B}^{- 1}$ is updated for the new basis.

What is stored. The inverse $A_{B}^{- 1}$ is $m \times m$ , together with the basis index list and the $m$ basic values. Nothing of size $m n$ is carried. Against a full tableau's $(m + 1) (n + 1)$ entries this is the whole difference in memory, and on a program with $n ≫ m$ it is a large one.

Why the inverse is updated, not recomputed. The new basis differs from the old in one column, so the new inverse is the old one premultiplied by an elementary matrix built from $u$ and the pivot row. An $O (m^{2})$ update rather than an $O (m^{3})$ inversion. Practical implementations store a factorisation of $A_{B}$ rather than the explicit inverse, for numerical stability, and refactorise periodically as update error accumulates.

What is identical to the tableau method. The entering rule, the ratio test, the step length, the basis sequence and the optimum. Given the same pivoting rule the two methods visit the same bases in the same order. They differ in bookkeeping, not in the path taken.

Assumptions and scope

The method starts from a basis with $A_{B}$ invertible and $A_{B}^{- 1} b \geq 0$ . Obtaining such a basis is a separate procedure, as with any simplex variant.
Pricing must cover every nonbasic column before optimality can be declared. A first-negative rule may stop early on an improving iteration, but the final iteration prices everything.
The explicit inverse is a teaching device. Implementations keep a factorisation of $A_{B}$ and solve two linear systems per iteration instead, because repeated inverse updates accumulate rounding error.
The choice of entering column may differ from a tableau run if a different pricing rule is used. The optimum is the same; the sequence of bases need not be.
Degeneracy behaves exactly as in the tableau method. A tie in the ratio test gives a degenerate basis, a zero step changes the basis without moving the point, and cycling is prevented by an anti-cycling rule rather than by the representation.

Worked material

Contrast

The same run, both ways

Take the program from the tableau unit: $min - 3 x_{1} - 2 x_{2}$ subject to $x_{1} + x_{2} + x_{3} = 4$ , $x_{1} + 3 x_{2} + x_{4} = 6$ , from $B = {3, 4}$ .

	Full tableau	Revised
Iteration 1, entering	scan objective row: ${\bar{c}}_{1} = - 3$	$p^{T} = (0, 0)$ , price $x_{1}$ : ${\bar{c}}_{1} = - 3$
Iteration 1, ratio test	read column 1: $4 / 1$ , $6 / 1$	$u = A_{B}^{- 1} A_{1} = (1, 1)^{T}$ , ratios $4$ , $6$
Iteration 1, update	row-reduce all 5 columns	update $A_{B}^{- 1}$ to $(\begin{matrix} 1 & 0 \\ - 1 & 1 \end{matrix})$
Iteration 2, test	scan objective row: $(0, 1, 3, 0)$	$p^{T} = (- 3, 0)$ ; ${\bar{c}}_{2} = 1$ , ${\bar{c}}_{3} = 3$
Result	optimal, $x = (4, 0, 0, 2)$ , $z = - 12$	optimal, $x = (4, 0, 0, 2)$ , $z = - 12$

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^{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 ${\bar{c}}_{2} = 1$ has an answer in the revised form, it is $c_{2} - p^{T} A_{2}$ , and $p$ came from $c_{B}^{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.

Common errors

Common misconception

The revised simplex method is a different algorithm from the tableau method, so it may visit different bases, take a different number of iterations, or reach a different optimum.

The Revised Simplex Method

Assumptions and scope

Worked material

The same run, both ways

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history