The Revised Simplex Method & Its Pivot Rules
A from-scratch tutorial on revised simplex, then a deep dive into the five pricing rules that decide which variable enters the basis: Dantzig, greatest increment, Bland, Devex, and steepest edge.
1. The linear program we're solving
Everything below assumes an LP in standard (computational) form:
\[ \max_{x}\; c^{\top} x \quad\text{subject to}\quad A x = b,\;\; x \ge 0, \]where \(A \in \mathbb{R}^{m \times n}\) with \(m\) constraints and \(n \ge m\) variables (inequalities have already been turned into equalities with slack variables). We assume \(A\) has full row rank \(m\).
The basis: the one object you must internalize
A basis is a choice of \(m\) columns of \(A\) that are linearly independent. Split the index set accordingly:
\[ A = \big[\, B \mid N \,\big], \qquad x = \begin{pmatrix} x_B \\ x_N \end{pmatrix},\qquad c = \begin{pmatrix} c_B \\ c_N \end{pmatrix}. \]\(B\) is the \(m\times m\) invertible basis matrix; \(N\) holds the remaining nonbasic columns. Set the nonbasic variables to zero, and the constraints force the rest:
\[ x_B = B^{-1} b, \qquad x_N = 0. \]This point \((x_B, x_N)\) is a basic feasible solution (BFS) whenever \(x_B \ge 0\); geometrically, it is a vertex of the feasible polyhedron. The simplex method walks from vertex to vertex, each step swapping one column between \(B\) and \(N\), always improving (or holding) the objective.
2. Why "revised" simplex?
The textbook tableau simplex method stores and updates the entire augmented tableau \(\big[\,B^{-1}A \mid B^{-1}b\,\big]\) every iteration: the \(m\times n\) constraint body \(B^{-1}A\) together with the right-hand-side column \(B^{-1}b\) (the current basic values \(x_B\)). That's a lot of numbers, most of which you never look at, and the repeated row operations accumulate floating-point error.
The revised simplex method keeps the same mathematics but stores far less. The key realization: every quantity you need in an iteration can be produced on demand from \(B^{-1}\) (or a factorization of \(B\)) plus the original data \(A, b, c\). You never form the full tableau.
| Tableau simplex | Revised simplex | |
|---|---|---|
| Stores | Full tableau \(\big[\,B^{-1}A \mid B^{-1}b\,\big]\): body + RHS column | Just \(B^{-1}\) (or an LU factorization of \(B\)); gets \(x_B=B^{-1}b\) on demand |
| Work / iter | \(O(mn)\) to update everything | \(O(m^2 + m\cdot(\text{cols priced}))\) |
| Memory | Dense \(mn\) | Sparse \(A\) + small \(B^{-1}\) data |
| Numerics | Error compounds in the tableau | Refactorize \(B\) periodically to reset error |
| Sparsity | Lost (fill-in) | Exploited (\(A\) stays sparse) |
The one-line summary: revised simplex is the simplex method reorganized around the factorization of \(B\), computing only the tableau entries it actually needs, which makes it the form used in every serious LP solver (HiGHS, CPLEX, Gurobi, …).
3. Anatomy of one iteration
A single revised-simplex iteration has five steps. The whole game of "pivot rules" lives in Step 2.
Step 1: Solve for the dual (BTRAN)
Compute the simplex multipliers \(y\) (a.k.a. the dual vector) by solving
\[ y^{\top} B = c_B^{\top} \quad\Longleftrightarrow\quad y = B^{-\top} c_B . \]Step 2: Pricing: pick the entering variable pivot rule lives here
For each nonbasic column \(a_j\), the reduced cost is
\[ \bar c_j = c_j - y^{\top} a_j . \]If \(\bar c_j \le 0\) for all nonbasic \(j\), the current vertex is optimal: stop. Otherwise some \(\bar c_j > 0\) tells us that increasing \(x_j\) will increase the objective. Which such \(j\) do we choose? That choice is the pivot rule. Call the winner \(q\).
Step 3: Solve for the search direction (FTRAN)
Find how the basic variables move as \(x_q\) increases:
\[ d = B^{-1} a_q . \]Step 4: Ratio test: pick the leaving variable
As \(x_q\) grows by \(t\), basic variables change as \(x_B - t\,d\). Keep them \(\ge 0\):
\[ t^{\star} = \min_{i:\, d_i > 0} \frac{(x_B)_i}{d_i}. \]The minimizing row \(p\) leaves the basis. (If no \(d_i > 0\), the LP is unbounded.)
Step 5: Update
Swap: \(q\) enters, \(p\) leaves. Update \(B^{-1}\) (product-form / Forrest–Tomlin update) or refactorize. Loop back to Step 1.
Where the names come from: BTRAN ("backward transformation") is the \(B^{-\top}\) solve in Step 1; FTRAN ("forward transformation") is the \(B^{-1}\) solve in Step 3. If you've read HiGHS internals, these are the two workhorse solves per iteration.
Before the loop: Phase 1
The five steps above assume you already have a feasible basis. Getting one is its own problem. The all-slack basis is primal-feasible for free whenever \(b \ge 0\), i.e. every "≤" row has a nonnegative right-hand side, which is the case in every demo on this page. Otherwise you run a Phase 1: add artificial variables and minimize their sum (the two-phase method), or penalize them with a large cost (big-M). Once the artificials are driven to zero you hold a feasible basis, and Phase 2 optimizes the real objective with exactly the machinery above.
Phase 1 is just simplex run on a different objective: same anatomy, same pricing, same factorization. There is nothing new to learn, only a different \(c\). (The dual method needs a different kind of start; see the mirror below.)
⇄ Dual simplex: the same iteration, mirrored
Primal simplex keeps primal feasibility (every iterate is a real vertex) and hunts for optimality. Dual simplex (Lemke, 1954) holds the opposite fixed: it keeps optimality and hunts for feasibility, using the same tableau machinery run in mirror order.
Two kinds of feasibility
Every basis has two separate "health checks":
- Primal feasibility: \(x_B = B^{-1}b \ge 0\): the basic variables are nonnegative, i.e. you're sitting on an actual vertex of the feasible region.
- Dual feasibility (= optimality): the reduced costs \(\bar c\) all have their optimal sign (for a min, \(\bar c_j \ge 0\) for every nonbasic \(j\); for a max, \(\bar c_j \le 0\)). This is exactly the "no improving column" stopping test.
A basis is optimal when it has both. The two methods hold one fixed and chase the other:
Primal simplex keeps primal feasibility (every iterate is a real vertex) and works toward optimality. Dual simplex keeps dual feasibility / optimality (every iterate has optimal-signed reduced costs but sits outside the feasible region, with some \(x_B < 0\)) and works toward primal feasibility. They approach the same optimal vertex from opposite sides: primal feasible-but-not-yet-optimal, dual optimal-cost-but-not-yet-feasible.
The mirror, step by step
The two selection choices swap order. Primal prices columns to pick who enters, then a ratio test over rows decides who leaves. Dual picks an infeasible basic variable to leave, then a ratio test over the pivot row decides who enters.
| Primal simplex | Dual simplex | |
|---|---|---|
| Maintains | primal feasibility \(x_B \ge 0\) | dual feasibility (\(\bar c\) optimal sign) |
| Seeks | optimality (\(\bar c\) sign) | primal feasibility \(x_B \ge 0\) |
| Starts from | a feasible vertex | an optimal-but-infeasible basis |
| Picks 1st | entering: price nonbasic \(\bar c_j\) (Dantzig/Devex/…) | leaving: a basic var with \((x_B)_i < 0\) (most-infeasible / dual pricing) |
| Picks 2nd | leaving: min-ratio \(\dfrac{(x_B)_i}{d_i}\) over rows \(d_i>0\) | entering: min-ratio \(\left|\dfrac{\bar c_j}{\alpha_{rj}}\right|\) over pivot-row entries of the right sign |
| Ratio test over | the FTRAN column \(d = B^{-1}a_q\) | the pivot row \(r\) of \(B^{-1}A\) |
| Failure detects | no leaving row → unbounded | no eligible entering col → infeasible |
| Best pivot rules | Devex, (primal) steepest edge | dual steepest edge, dual Devex |
Note both still run BTRAN and FTRAN each iteration; the linear algebra (LU of \(B\), the eta updates) is identical. Only the selection policy flips.
Anatomy of a dual iteration
Set this beside the primal five steps of §3: it's the same skeleton with the two choices swapped:
Step 1: Pick the leaving variable (the primal-infeasibility test)
Compute \(x_B = B^{-1}b\) (an FTRAN). If \(x_B \ge 0\) you're primal-feasible, hence optimal: stop. Otherwise choose a row \(p\) with \((x_B)_p < 0\): the "most infeasible" one, or one chosen by dual steepest-edge pricing. That basic variable leaves.
Step 2: Compute the pivot row (BTRAN)
Extract row \(p\) of \(B^{-1}A\): first \(\rho = e_p^{\top}B^{-1}\) (a BTRAN with the unit vector \(e_p\)), then the row entries \(\alpha_{pj} = \rho\cdot a_j\) for each nonbasic \(j\). (Primal Step 1's BTRAN produced the price vector \(y\); here the BTRAN produces a row of the tableau.)
Step 3: Dual ratio test (pick the entering variable)
As the leaving variable is dragged back to its bound, every reduced cost shifts. To keep them all at their optimal sign, only nonbasic columns with \(\alpha_{pj}\) of the right sign are eligible; among those pick \(q = \arg\min_j \left|\dfrac{\bar c_j}{\alpha_{pj}}\right|\). That column enters. If none are eligible, no basis can repair this row → the LP is primal-infeasible (stop).
Step 4: Ratio → step length, update the reduced costs
The minimizing ratio is exactly how far the reduced costs can move before one would flip sign; take that step. \(q\) enters, \(p\) leaves.
Step 5: Update \(B^{-1}\) / LU
Identical to primal: FTRAN the entering column, append the eta / patch the LU, and loop.
The symmetry in one line: primal prices columns (BTRAN → \(y\)) to choose who enters, then ratio-tests a column to choose who leaves. Dual prices a row (BTRAN → a row of \(B^{-1}\)) to choose who leaves, then ratio-tests that row to choose who enters. Each does one BTRAN and one FTRAN per iteration, just wired in the opposite order.
Where the dual starts (its Phase 1)
Primal needs a primal-feasible basis; dual needs a dual-feasible one: reduced costs already at their optimal sign. That is free whenever the costs start with the right sign (e.g. minimizing with \(c \ge 0\)); otherwise you need a dual Phase 1 (a cost-shifting / composite subproblem). The two Phase-1s are themselves duals: making the primal feasible is, in dual space, making the dual optimal.
Why dual simplex is the workhorse
Its superpower is warm-starting. In branch-and-bound and cutting-plane methods you solve an LP, then add a constraint (a branching bound, or a cut). Adding a constraint can make the old optimal basis primal-infeasible (the previous solution now violates the new row), but it stays dual-feasible, because the reduced costs keep their sign. That is exactly the dual simplex's starting state, so a handful of dual pivots restore optimality instead of re-solving from scratch. The same is true when you only change the right-hand side \(b\). This is why dual (steepest-edge) simplex is the default LP method for the node solves inside virtually every MILP solver, and often the overall default.
# DUAL simplex iteration (max cᵀx; dual-feasible start with some x_B < 0) loop: x_B = B⁻¹b if x_B ≥ 0: return OPTIMAL # primal feasibility reached p = argmin_i (x_B)_i # leaving var = most infeasible (BTRAN-priced) ρ = row p of B⁻¹A # the pivot row (one BTRAN + spread) if ρ_j ≥ 0 for all nonbasic j: return INFEASIBLE q = argmin over {j : ρ_j < 0} of |c̄_j / ρ_j| # dual ratio test → entering pivot(q in, p out); update B⁻¹ / LU # same FTRAN + eta update as primal
4. Under the hood: factorization & the one-column update
In §2 we claimed revised simplex stores "just \(B^{-1}\) (or an LU factorization)" and updates it cheaply, costing only \(\sim O(m^2)\) per iteration instead of \(O(m^3)\). Those two claims rest on two tricks, and they're the real source of the method's speed:
- Factorize \(B\), never invert it. (§4.1)
- Update instead of refactorizing from scratch, because only one column changed. (§4.2)
4.1 Factorize, don't invert (LU)
Look back at the iteration. Steps 1 and 3 never actually need the matrix \(B^{-1}\) itself; they need to solve linear systems whose coefficient matrix is \(B\):
\[ \text{FTRAN: } B\,d = a_q, \qquad\qquad \text{BTRAN: } B^{\top} y = c_B . \]An explicit inverse is the wrong tool for solving systems:
- Forming \(B^{-1}\) costs \(O(m^3)\).
- \(B^{-1}\) is dense even when \(B\) is sparse: catastrophic fill-in for large problems.
- Multiplying by an explicit inverse amplifies rounding error.
So instead we compute, once, an LU factorization
\[ B = L\,U \qquad (\text{plus row/column permutations for stability and sparsity}), \]with \(L\) lower-triangular and \(U\) upper-triangular. Triangular systems solve by plain substitution, in time proportional to the number of nonzeros:
\[ \underbrace{B\,d = a_q}_{\text{FTRAN}}:\;\; L\,w = a_q \;\text{(forward subst)},\;\; U\,d = w \;\text{(back subst)}; \] \[ \underbrace{B^{\top} y = c_B}_{\text{BTRAN}}:\;\; (LU)^{\top}= U^{\top}L^{\top}\Rightarrow\; U^{\top} z = c_B,\;\; L^{\top} y = z . \]With a good fill-reducing ordering, \(L\) and \(U\) stay nearly as sparse as \(B\), so each solve is cheap and numerically far more stable than hitting a dense inverse.
Mental image: \(B^{-1}\) is a dense wall of \(m^2\) numbers. Its LU factorization is two sparse triangles you slide a substitution sweep through: same answer, a fraction of the work, and much better numerics. That's why no serious solver ever stores the inverse.
4.2 The one-column swap → a rank-one update
Here's the part that makes simplex specifically so efficient. From one iteration to the next, the basis changes in exactly one column: the entering column \(a_q\) replaces the leaving column (the \(p\)-th column of \(B\)). Everything else is byte-for-byte identical. Refactorizing the whole new basis \(\bar B\) from scratch each iteration would throw that structure away.
Algebraically, the new basis is a rank-one modification of the old one:
\[ \bar B = B + (a_q - B e_p)\,e_p^{\top}, \]where \(e_p\) is the \(p\)-th unit vector. By the Sherman–Morrison formula, its inverse is a rank-one update of \(B^{-1}\), and it takes a beautifully simple form built entirely from the FTRAN vector you already computed in Step 3:
\[ d = B^{-1} a_q \qquad\Longrightarrow\qquad \bar B^{-1} = E\,B^{-1}, \]where \(E\) is an eta matrix: the identity, with its \(p\)-th column replaced by
\[ \eta = \Big(\,-\tfrac{d_1}{d_p},\ \dots,\ \tfrac{1}{d_p},\ \dots,\ -\tfrac{d_m}{d_p}\,\Big)^{\!\top}, \qquad \tfrac{1}{d_p}\ \text{sits in row } p . \]Concretely, for \(m=4\) and a pivot in row \(p=2\), \(E\) is just the identity with one special column:
\[ E=\begin{pmatrix} 1 & -d_1/d_2 & 0 & 0\\[2pt] 0 & \ \ 1/d_2 & 0 & 0\\[2pt] 0 & -d_3/d_2 & 1 & 0\\[2pt] 0 & -d_4/d_2 & 0 & 1 \end{pmatrix} \quad\begin{array}{l}\\[-2pt]\leftarrow\ \text{only column } p=2\\ \quad\ \text{differs from } I\end{array} \]The punchline: a pivot's update is essentially free: \(\eta\) is built entirely from \(d\), which the iteration already computed for the ratio test. The "swap one column" geometry becomes "append one vector" algebra.
Product form of the inverse (PFI)
Apply this repeatedly. Starting from a factorized basis \(B_0\), after \(k\) pivots:
\[ B_k^{-1} = E_k\,E_{k-1}\cdots E_1\, B_0^{-1}. \]So the solver keeps the original LU of \(B_0\) plus a growing list of eta vectors, one per pivot. FTRAN and BTRAN become: do the base triangular solves, then apply each eta in turn, and each eta application is just \(O(m)\) (really \(O(\text{nnz}(\eta))\)).
Why you still refactorize periodically
Two things grow with the eta list, which is why §2 said "refactorize \(B\) periodically":
- Time: after \(k\) pivots, every solve must apply \(k\) etas, so solves get steadily slower the longer you go.
- Error: each rank-one update compounds a little floating-point error.
So every \(\sim\)50–100 iterations (or once the list gets long / accuracy drifts), the solver reinverts: it recomputes a fresh sparse LU of the current basis and discards the eta list. This caps both the per-solve cost and the accumulated error, and it is exactly why the amortized work is \(\sim O(m^2)\) per iteration rather than a full \(O(m^3)\) refactorization every time.
What real solvers do: naive PFI just appends eta vectors, which slowly destroys sparsity. The Bartels–Golub and Forrest–Tomlin updates are smarter: instead of tacking on an eta, they surgically modify the LU factors (patch up \(U\)) when a column is replaced, preserving sparsity far better. That's what HiGHS / CPLEX / Gurobi actually run, but the eta-vector picture above is the right mental model for why a pivot is cheap.
⇄ Dual simplex: identical linear algebra, different right-hand sides
Nothing in this section changes for the dual method. It factorizes the same \(B\) as \(PB = LU\), solves with the same forward/back substitutions, and updates with the same eta / Forrest–Tomlin machinery. The only difference is what the two solves are asked for:
| Solve | Primal uses it for… | Dual uses it for… |
|---|---|---|
| FTRAN \(B\,\square = \text{rhs}\) | \(d = B^{-1}a_q\): the direction of the entering column | \(x_B = B^{-1}b\): which basic variable is infeasible |
| BTRAN \(B^{\top}\square = \text{rhs}\) | \(y = B^{-\top}c_B\): the prices, to get reduced costs | \(\rho = B^{-\top}e_p\): row \(p\) of \(B^{-1}\), i.e. the pivot row |
So the dual's BTRAN is solved with the unit vector \(e_p\) in place of \(c_B\): it extracts row \(p\) of \(B^{-1}\), which then spreads across the nonbasic columns to give the pivot row \(\alpha_{pj} = \rho \cdot a_j\). Same triangular solves, same factors, different right-hand side, which is exactly why one factorization serves both methods.
5. Pricing is the heart of the method
Steps 1, 3, 4, 5 are fixed linear algebra. Step 2 is a policy decision. Usually many reduced costs are positive, so many columns are eligible to enter. The pivot rule is the tie-breaker, and it has an outsized effect:
- Iteration count. A good rule reaches the optimum in fewer vertices. Cheap-per-step rules can take exponentially many steps on adversarial inputs (Klee–Minty).
- Cost per iteration. A "smarter" rule that inspects more information per column costs more per iteration. The art is trading per-step cost against step count.
- Termination. Under degeneracy (a basic variable already at zero, so \(t^\star = 0\)), naive rules can cycle forever. Some rules guarantee they can't.
The five rules below sit on a clear spectrum from "cheap and dumb" to "expensive and sharp":
| Rule | What it measures | Per-iter cost | Anti-cycling? |
|---|---|---|---|
| Bland | Smallest index with \(\bar c_j>0\) | cheapest | ✓ guaranteed |
| Dantzig | Most positive \(\bar c_j\) (best rate) | cheap | ✗ can cycle |
| Greatest increment | Largest actual gain \(\bar c_j\cdot t^\star_j\) (rate × feasible step) | very expensive | ✗ can cycle |
| Devex | \(\bar c_j\) scaled by an approximate edge norm | moderate | ~ in practice |
| Steepest edge | \(\bar c_j\) scaled by the true edge norm | expensive | ~ in practice |
Bound flipping: the free long step
Production solvers use the bounded-variable form \(l \le x \le u\), where a nonbasic variable rests at either its lower or its upper bound (not just 0). That unlocks a move with no basis change at all:
A bound flip sends a nonbasic variable straight from one bound to the other. The basic variables just slide by \((\text{bound change}) \times (\text{its column direction } B^{-1}a_j)\); \(B\), \(B^{-1}\), and the LU are untouched: no pivot, no refactorization. It's a genuinely free step that can move the solution a long way.
- Primal: if the entering variable would reach its own opposite bound before any basic variable hits a bound, it simply flips (the bound-flipping ratio test) and no variable leaves the basis.
- Dual: the long-step (bound-flipping) dual ratio test (Maros; Koberstein & Suhl) lets the entering choice pass through several breakpoints, flipping the intervening nonbasic variables between their bounds as it goes, and taking a much larger dual step per iteration. It's one of the biggest practical speedups in modern dual simplex.
The takeaway: not every "step" of simplex is a pivot. Bound flips let both methods make progress while keeping the same basis factorization: cheap mileage between the expensive basis changes.
⇄ Dual simplex: pricing rows instead of columns
Primal pricing scans nonbasic columns looking for an improving reduced cost. Dual pricing scans basic rows looking for an infeasibility, and the two choices happen in the opposite order:
- Pick the leaving variable first. Among rows with \((x_B)_i < 0\), choose one. "Most infeasible" (\(\min_i (x_B)_i\)) is the direct analogue of Dantzig's rule, and it carries the same flaw: it is a raw magnitude, blind to the geometry. Better weightings exist (see the dual mirror in §6).
- Then the dual ratio test picks the entering column. Among nonbasic \(j\) whose pivot-row entry \(\alpha_{pj}\) has the sign that preserves optimality, take \(q = \arg\min_j \left|\bar c_j / \alpha_{pj}\right|\), the first reduced cost that would flip sign as the step is taken. If nothing is eligible, no basis can repair that row and the LP is primal-infeasible.
The failure modes mirror too: a primal ratio test that finds no leaving row means unbounded; a dual ratio test that finds no entering column means infeasible.
Bound flipping mirrors as well: the dual's long-step ratio test (above) is precisely this dual ratio test allowed to walk past several breakpoints, flipping the intervening nonbasic variables between their bounds as it goes.
6. The pivot rules
6.1 Dantzig's rule: "most positive reduced cost"
The original rule (Dantzig, 1947). Pick the entering variable with the steepest per-unit improvement in the objective:
\[ q = \arg\max_{j\,:\,\bar c_j > 0}\ \bar c_j . \]Intuition
\(\bar c_j\) is the rate at which the objective rises per unit increase of \(x_j\). Dantzig greedily grabs the column promising the fastest climb. Simple, and free once you've priced all columns.
The flaw
The rate says nothing about how far you can actually move. A column with a hugely positive \(\bar c_j\) might hit a constraint almost immediately (ratio test gives tiny \(t^\star\)), yielding negligible actual progress. Dantzig is fooled by units and scaling: multiply one column's data by 1000 and its reduced cost changes, so the rule is not scale-invariant.
Worst case: Klee & Minty (1972) built a "squashed cube" LP with \(n\) variables where Dantzig's rule visits all \(2^n\) vertices, which takes exponential time. And under degeneracy Dantzig can cycle. In practice it's still decent and very cheap, but it's rarely the default in modern solvers.
6.2 Greatest increment: "largest actual objective gain"
Also called the largest-increase or greatest-improvement rule. Where Dantzig maximizes the rate of improvement (\(\bar c_j\), the gain per unit of \(x_j\)), greatest increment maximizes the actual gain realized on the step, the rate multiplied by how far the ratio test lets you travel:
\[ q = \arg\max_{j\,:\,\bar c_j>0}\ \bar c_j\cdot t^\star_j, \qquad t^\star_j = \min_{i:\,(d_j)_i>0}\frac{(x_B)_i}{(d_j)_i},\quad d_j = B^{-1}a_j . \]Intuition
Dantzig is fooled when a steep column slams into a constraint immediately (tiny \(t^\star\)). Greatest increment refuses to be fooled: it looks ahead to where you would actually stop and scores the genuine objective increase. On a per-step basis it makes the most progress of any rule here.
The cost, and why there's no cheap version
To score a column you need its direction \(d_j = B^{-1}a_j\) (an FTRAN) and a full ratio test, for every eligible column. That's roughly tableau-level work per iteration, making it the most expensive rule on this page. Unlike Devex (which cheaply approximates steepest edge via a weight recurrence), greatest increment has no analogous cheap approximation: \(t^\star_j\) depends on the entire current \(x_B\) and changes structurally every pivot, so there's nothing to carry forward. The practical proxy is a Dantzig pre-screen: shortlist the top-\(k\) most-positive reduced costs, then run the full greatest-increment ratio-test scoring only on that shortlist (a form of partial / multiple pricing).
Two weaknesses: (1) Degeneracy blinds it: if any \((x_B)_i=0\) with \((d_j)_i>0\) then \(t^\star_j=0\) and the score collapses to \(0\), so it can't tell good directions apart at a degenerate vertex (steepest edge, being purely geometric, has no such problem). (2) Worst case is still exponential (Jeroslow, 1973). Biggest per-step progress ≠ fewest steps overall.
6.3 Bland's rule: "smallest index"
Among all eligible columns, pick the one with the smallest index, and use the same smallest-index tie-break in the ratio test for the leaving variable:
\[ q = \min\{\, j : \bar c_j > 0 \,\}. \]Why anyone would use such a dumb rule
Bland's rule (1977) makes no attempt to pick a good column, only a consistent one. Its entire value is a theorem:
Bland's theorem. With smallest-index selection for both the entering and leaving variable, the simplex method cannot cycle and is guaranteed to terminate, even under degeneracy.
The intuition: a consistent total order on indices prevents the method from ever revisiting a basis it has seen before in a degenerate stall.
How it's actually used
Nobody runs Bland from the start; it's slow (it ignores objective magnitude entirely and tends to crawl). Instead it's a fallback: solvers run Dantzig/Devex/steepest-edge for speed, and only switch to Bland (or use a perturbation/lexicographic scheme) when they detect a degenerate stall, to guarantee escape. Think of it as the cycle-breaking safety net.
6.4 Devex: "approximate steepest edge"
Devex (Paula Harris, 1973) fixes Dantzig's scaling flaw without paying steepest-edge prices. Instead of the raw \(\bar c_j\), it scores each column by reduced cost divided by an approximate column norm:
\[ q = \arg\max_{j\,:\,\bar c_j>0}\ \frac{\bar c_j^{\,2}}{\gamma_j}, \]where \(\gamma_j\) is a reference weight approximating \(\|B^{-1}a_j\|^2\), the squared length of the step direction.
The trick: a reference frame
Computing the true norm \(\|B^{-1}a_j\|^2\) every iteration is what makes steepest edge expensive. Devex instead:
- Fixes a reference framework (a snapshot of the current set of nonbasic variables), initializing all weights \(\gamma_j = 1\).
- Measures lengths relative to that reference frame, not the full space, which is much cheaper.
- Updates the weights cheaply after each pivot using a recurrence, never recomputing from scratch.
- Periodically resets the reference frame when the approximation drifts too far from reality.
Why it wins
Devex is approximately scale-invariant and captures the "how far can I move" information Dantzig ignores, at a fraction of steepest-edge cost. It is the default primal pricing rule in many solvers (it's what most people run in practice): an excellent cost/quality sweet spot.
6.5 Steepest edge: "true steepest ascent along an edge"
Goldfarb & Reid (1977). The most principled rule: each candidate entering variable corresponds to an edge of the polyhedron leaving the current vertex. Steepest edge picks the edge along which the objective increases fastest per unit distance actually travelled in \(x\)-space: true steepest ascent, not just per-unit-of-\(x_j\).
\[ q = \arg\max_{j\,:\,\bar c_j>0}\ \frac{\bar c_j^{\,2}}{\gamma_j}, \qquad \gamma_j = \big\| \, B^{-1} a_j \,\big\|^2 + 1 . \]The distinction from Dantzig, geometrically
Dantzig measures ascent per unit change in the single coordinate \(x_j\). But moving along that edge changes all the basic variables too, by \(d = B^{-1}a_j\). The true distance moved in the full space scales with \(\|(d, 1)\|\). Steepest edge normalizes by exactly this length, so it is perfectly scale-invariant and picks the genuinely best direction.
The cost
The exact weights \(\gamma_j\) are expensive: computing \(\|B^{-1}a_j\|^2\) for every column is roughly another full tableau's worth of work. The Goldfarb–Reid contribution is a recurrence that updates all \(\gamma_j\) exactly after a pivot for only \(O(m)\)-ish extra work per iteration, instead of recomputing from scratch. This is what makes it viable at all.
The trade-off in one sentence: steepest edge usually takes the fewest iterations of any rule here, but each iteration costs more, so it wins on large, hard LPs where iteration count dominates, and the dual variant (dual steepest edge) is the workhorse default for many solvers' dual simplex.
Note Devex and steepest edge share the same scoring formula \(\bar c_j^2/\gamma_j\); the only difference is whether \(\gamma_j\) is the exact edge norm (steepest edge) or a cheap running approximation of it (Devex). That's the cleanest way to remember the relationship.
⇄ Dual simplex: the same five rules, applied to rows
Every rule above has a dual counterpart. They score rows (candidate leaving variables) rather than columns, but the ideas map one-for-one:
| Primal (choose the entering column) | Dual (choose the leaving row) |
|---|---|
| Dantzig: largest \(\bar c_j\) | Most infeasible: most negative \((x_B)_i\). Same greed, same blindness to geometry. |
| Greatest increment: largest \(|\bar c_j|\,t^\star_j\) | Largest actual dual objective gain: same idea, same prohibitive cost. |
| Steepest edge: \(\bar c_j^2/\|B^{-1}a_j\|^2\) | Dual steepest edge (DSE): infeasibility scaled by the row norm \(\|e_p^{\top}B^{-1}\|^2\). |
| Devex: cheap running weights | Dual Devex: the same recurrence, on rows. |
| Bland: smallest index | Smallest-index leaving row: the same anti-cycling safety net. |
The one that matters: dual steepest edge is the default pricing rule for dual simplex in essentially every serious solver, and, paired with the dual method, the default LP algorithm for the node solves inside MILP. The reason is the same as in the primal (normalizing by the norm makes the choice scale-invariant); the payoff is bigger simply because dual simplex is run so much more often.
7. Side-by-side comparison
| Rule | Selection score | Scale-invariant? | Iterations | Cost / iter | Best use |
|---|---|---|---|---|---|
| Bland | min index \(j\) with \(\bar c_j>0\) | n/a | many | trivial | Anti-cycling fallback only |
| Dantzig | \(\max_j \bar c_j\) | no | many–medium | cheap | Small/easy LPs, teaching |
| Greatest increment | \(\max_j |\bar c_j|\,t^\star_j\) | no | few–medium | very expensive | Rarely used directly (ratio test per column); pre-screen hybrid |
| Devex | \(\max_j \bar c_j^2/\gamma_j\), \(\gamma\) approx. | ≈ yes | few–medium | moderate | Excellent general default |
| Steepest edge | \(\max_j \bar c_j^2/\gamma_j\), \(\gamma\) exact | yes | fewest | expensive | Large/hard LPs (esp. dual) |
The mental model: all four answer the same question ("of the columns that would improve the objective, which one?") and differ only in how much they normalize the raw reduced cost by the true geometry of the step. Bland ignores the objective entirely (pick by index); Dantzig uses raw rate; Devex uses an approximate norm; steepest edge uses the exact norm.
8. Worked micro-example: Dantzig vs. the rest
Suppose at some vertex we've priced three eligible nonbasic columns and computed the direction norms:
| Column \(j\) | \(\bar c_j\) | \(\gamma_j=\|B^{-1}a_j\|^2+1\) | Dantzig score \(\bar c_j\) | Devex/SE score \(\bar c_j^2/\gamma_j\) |
|---|---|---|---|---|
| \(x_3\) | \(12\) | \(400\) | 12 ← Dantzig picks | \(0.36\) |
| \(x_5\) | \(5\) | \(2\) | 5 | 12.5 ← steepest edge picks |
| \(x_7\) | \(8\) | \(50\) | 8 | \(1.28\) |
Dantzig grabs \(x_3\) for its huge \(12\) reduced cost, but \(\gamma_3=400\) means that edge is nearly flat and you'll barely move before hitting a constraint. Steepest edge sees through this: \(x_5\) has a smaller rate but a short, productive edge (\(\gamma_5=2\)), giving the best objective gain per unit distance actually travelled. This is exactly the trap Klee–Minty exploits against Dantzig, and exactly why norm-scaled rules dominate on hard problems.
9. The same LP under all five rules
The micro-example in §8 was hypothetical. Here we take a complete LP and run it to optimality, watching exactly which column each rule chooses at every step. We solve
\[ \max\; 2x_1 + 3x_2 \quad\text{s.t.}\quad x_1 + x_2 \le 4,\;\; x_1 + 2x_2 \le 6,\;\; x \ge 0, \]which in standard form adds slacks \(s_1, s_2\). Index the variables \(x_1{=}1,\ x_2{=}2,\ s_1{=}3,\ s_2{=}4\); the data is
\[ A=\begin{pmatrix}1&1&1&0\\1&2&0&1\end{pmatrix},\quad b=\begin{pmatrix}4\\6\end{pmatrix},\quad c=(2,3,0,0). \]Start at the origin with basis \(\{s_1,s_2\}\). Because the pivot rule only touches Step 2, and because every step after the first in this LP has only one eligible column, iteration 1 is the only place the rules disagree.
The decision point: iteration 1
At the origin \(B^{-1}=I\) and \(y=0\), so reduced costs equal the raw objective coefficients: \(\bar c_1=2\) and \(\bar c_2=3\). Both eligible. Each rule scores them differently:
| Rule | What it computes | Score \(x_1\) | Score \(x_2\) | Picks |
|---|---|---|---|---|
| Dantzig | most positive \(\bar c_j\) | \(2\) | \(3\) | \(x_2\) |
| Greatest increment | \(\bar c_j\cdot t^\star_j\) (\(x_B=(4,6)\)) | \(2\cdot4=8\) | \(3\cdot3=9\) | \(x_2\) |
| Bland | smallest eligible index | index 1 | index 2 | \(x_1\) |
| Steepest edge | \(\bar c_j^2/(\|B^{-1}a_j\|^2+1)\) | \(\tfrac{4}{3}\approx1.33\) | \(\tfrac{9}{6}=1.5\) | \(x_2\) |
| Devex | \(\bar c_j^2/\gamma_j\), \(\gamma_j{=}1\) at reference frame | \(4\) | \(9\) | \(x_2\) |
The steepest-edge / Devex arithmetic in full (since \(B^{-1}=I\), \(B^{-1}a_j=a_j\)):
\[ x_1:\ a_1=(1,1)\Rightarrow\|a_1\|^2=2\Rightarrow\gamma_1=3\Rightarrow \tfrac{2^2}{3}=1.33,\qquad x_2:\ a_2=(1,2)\Rightarrow\|a_2\|^2=5\Rightarrow\gamma_2=6\Rightarrow \tfrac{3^2}{6}=1.5 . \]The interesting near-miss: steepest edge penalizes \(x_2\): its reduced cost is bigger \((3)\) but its edge is longer \((\gamma=6\) vs \(3)\), so the margin nearly closes (1.50 vs 1.33). A slightly flatter objective on \(x_2\) would flip steepest edge to \(x_1\) while Dantzig still chose \(x_2\). That's scale-sensitivity made concrete. Bland alone picks \(x_1\), purely because \(1<2\); it never looks at a score.
The two resulting paths
So the rules split. Both routes reach the optimum \((2,2)\), \(z=10\), in two pivots, but along opposite edges of the feasible region.
Path A: Dantzig / Greatest increment / Devex / Steepest edge (\(x_2\) enters first)
| Iter | Vertex | Eligible candidates | Choice | Why |
|---|---|---|---|---|
| 1 | (0, 0) | \(x_1\,(2)\), \(x_2\,(3)\) | \(x_2\) | all four score \(x_2\) highest |
| 2 | (0, 3) | only \(x_1\) \((\bar c_1{=}{+}0.5;\ \bar c_4{=}{-}1.5\) ✗) | \(x_1\) | forced: one candidate |
| 3 | (2, 2) | none \((\bar c_3{=}\bar c_4{=}{-}1)\) | none | optimal, \(z=10\) |
Route: (0,0) → (0,3) → (2,2).
Path B: Bland (\(x_1\) enters first)
| Iter | Vertex | Eligible candidates | Choice | Why |
|---|---|---|---|---|
| 1 | (0, 0) | \(x_1\,(2)\), \(x_2\,(3)\) | \(x_1\) | smallest index |
| 2 | (4, 0) | only \(x_2\) \((\bar c_2{=}{+}1;\ \bar c_3{=}{-}2\) ✗) | \(x_2\) | forced: one candidate |
| 3 | (2, 2) | none \((\bar c_3{=}\bar c_4{=}{-}1)\) | none | optimal, \(z=10\) |
Route: (0,0) → (4,0) → (2,2). Iteration-2 detail: basis \(\{x_1,s_2\}\), \(B^{-1}=\big[\begin{smallmatrix}1&0\\-1&1\end{smallmatrix}\big]\), \(y=(2,0)\), so \(\bar c_2=3-2=1\).
The lesson: pivot rules diverge only at a vertex with two or more eligible columns. Once a vertex offers a single eligible candidate, all five rules agree by necessity. So a rule's "personality" shows up precisely at the branching vertices, which is exactly where the shortest-pivot-path question lives. (Note this gentle LP doesn't separate Dantzig, greatest increment, Devex and steepest edge, which all pick \(x_2\). The next section builds a vertex where they split.)
⇄ Dual simplex: how it would attack a demo problem
First, an honest observation about the demos on this page: their all-slack basis has \(b \ge 0\), so it is primal-feasible but not dual-feasible (for a max with \(c > 0\), every \(\bar c_j = c_j > 0\)). Primal simplex can start immediately; the dual would need a dual Phase 1 first. These LPs are primal's home turf, and that is the point: you pick the method whose feasibility you already have.
So here is a small LP built the other way round, where the slack basis is already optimal in cost and merely infeasible, i.e. tailor-made for the dual:
Worked example: two dual pivots
A problem tailor-made for the dual: the all-slack start is already optimal in cost, just infeasible.
\[ \min\; 2x_1 + 3x_2 \quad\text{s.t.}\quad x_1 + x_2 \ge 4,\;\; x_1 + 3x_2 \ge 6,\;\; x \ge 0. \]Flip the \(\ge\) rows to \(\le\) (multiply by \(-1\)) and add slacks, so \(A=\big[\begin{smallmatrix}-1&-1&1&0\\-1&-3&0&1\end{smallmatrix}\big]\), \(b=(-4,-6)\). Start with the slack basis \(\{s_1,s_2\}\): the reduced costs are \((2,3,0,0)\ge 0\), so the basis is dual feasible, but \(x_B=(-4,-6)<0\), so it is primal infeasible. Perfect dual start.
| Iter | Basis | \(x_B\) | Leaving (most neg.) | Dual ratio test \(|\bar c_j/\alpha_{rj}|\) | Entering |
|---|---|---|---|---|---|
| 1 | \(\{s_1,s_2\}\) | \((-4,-6)\) | \(s_2\) \((-6)\) | \(x_1\!:\tfrac{2}{1}{=}2\), \(x_2\!:\tfrac{3}{3}{=}1\) ← | \(x_2\) |
| 2 | \(\{s_1,x_2\}\) | \((-2,\ 2)\) | \(s_1\) \((-2)\) | \(x_1\!:\tfrac{1}{2/3}{=}1.5\) ←, \(s_2\!:\tfrac{1}{1/3}{=}3\) | \(x_1\) |
| 3 | \(\{x_1,x_2\}\) | \((3,\ 1)\) | none \(<0\) | n/a | optimal, \(z=9\) |
In \((x_1,x_2)\) the dual iterates are \((0,0)\to(0,2)\to(3,1)\): the first two lie outside the feasible region (their cost is optimal for the current basis, but they violate the constraints), and the method tightens onto the optimal vertex \((3,1)\) from below. A primal solve of the same LP would instead crawl along the feasible boundary. Both land on \((3,1)\), \(z=9\).
10. Distinguishing greatest increment, Devex & steepest edge
These three rules all look like "Dantzig but smarter," which is why they're easy to confuse. The fix is to see that they answer three different questions:
| Rule | Question it answers | Score | Uses |
|---|---|---|---|
| Greatest increment | "Biggest actual gain this step?" | \(\max\ \bar c_j\cdot t^\star_j\) | the feasibility-limited step: ratio test, depends on \(x_B\), only positive entries of \(d_j\) bind |
| Steepest edge | "Steepest ascent per unit distance?" | \(\max\ \bar c_j^2/(\|d_j\|^2+1)\) | the geometric edge length: full norm, all entries of \(d_j\) |
| Devex | (cheap approximation of steepest edge) | \(\max\ \bar c_j^2/\tilde\gamma_j\) | approximate edge length \(\tilde\gamma_j\approx\|d_j\|^2\) via reference weights |
The lever that splits greatest increment from steepest edge: the ratio test only sees positive components of \(d_j\) (those bind), but the edge norm includes all components. So a direction with a big negative component is geometrically long (steepest edge hates it) yet doesn't hit a wall early (greatest increment loves the long feasible step). That one fact makes them disagree.
Demo: one vertex, three different winners
Current basic values \(x_B=(12,12)\). Three eligible candidates A, B, C, each with reduced cost \(\bar c\) and direction \(d=B^{-1}a\):
| Cand. | \(\bar c\) | \(d=B^{-1}a\) | Dantzig \(\bar c\) | Ratio test \(t^\star\) | Greatest incr. \(\bar c\,t^\star\) | \(\|d\|^2{+}1\) | Steepest edge \(\bar c^2/\gamma\) |
|---|---|---|---|---|---|---|---|
| A | \(2\) | \((2,\ 0)\) | \(2\) | \(12/2=6\) | \(2\cdot6=12\) | \(5\) | \(4/5=0.80\) ← |
| B | \(3\) | \((3,\ 3)\) | \(3\) ← | \(\min(4,4)=4\) | \(3\cdot4=12\) | \(19\) | \(9/19=0.47\) |
| C | \(1\) | \((0.5,\ -4)\) | \(1\) | \(12/0.5=24\) | \(1\cdot24=24\) ← | \(17.25\) | \(1/17.25=0.06\) |
On the very same data, three different columns win:
- Dantzig → B. Steepest per-unit rate \((3)\), but blind: B slams into a constraint at \(t^\star=4\).
- Greatest increment → C. Its rate is feeble \((1)\), but its negative component \((-4)\) never binds and its positive component is tiny, so it travels a huge feasible distance \((t^\star=24)\) → the biggest actual gain \((24)\).
- Steepest edge → A. Per unit of Euclidean distance, A climbs fastest. C's big negative component makes its edge geometrically long \((\|d\|^2=16.25)\), so its slope is shallow. Steepest edge rejects exactly the direction greatest increment loved.
Devex cheaply approximates the steepest-edge norms. Right after a reference-frame reset its weights equal the exact norms, so it reproduces steepest edge and also picks A; as it drifts it stays close. (E.g. approximate weights \(\tilde\gamma=(4,16,12)\) give scores \(1.00 / 0.56 / 0.08\) → still A.)
The one-sentence separation: greatest increment maximizes how far × how steep (realized gain); steepest edge maximizes how steep per unit distance (slope), ignoring how far feasibility lets you travel; Devex is just a cheap stand-in for steepest edge.
Try it yourself: walk the simplex path
This is a real 2-variable, 2-constraint LP. Pick a rule, then click Step ▶ to pivot to the next corner that rule chooses; keep stepping until it reaches the optimum. At every vertex the engine does the full revised-simplex iteration (build \(B^{-1}\), price the nonbasic columns, ratio test), so it works at any corner, not just the origin. The badges on the graph show what each rule would choose from the current corner, so you can see exactly where the methods part ways.
Now in 3D: a polyhedron you can rotate
The same ideas in three variables. Here the feasible region is a real polyhedron, and the simplex method crawls along its edges from corner to corner. Pick a rule and click Step ▶; drag the picture to rotate it (or use the rotate/tilt sliders). The engine runs full revised simplex with 3×3 \(B^{-1}\), so it works at every corner.
Appendix: Revised simplex in pseudocode
# max cᵀx s.t. Ax = b, x ≥ 0 (A is m×n, full row rank) given a feasible basis B (index set), with basis matrix A[:,B] loop: # --- Step 1: BTRAN (dual multipliers) --- y = solve(Bᵀ, c[B]) # yᵀB = c_Bᵀ # --- Step 2: PRICING (choose entering column q) --- for each nonbasic j: cbar[j] = c[j] - yᵀ·A[:,j] if cbar[j] ≤ 0 for all j: return OPTIMAL q = select_entering(cbar, weights) # ← Dantzig / greatest incr. / Bland / Devex / steepest edge # --- Step 3: FTRAN (search direction) --- d = solve(B, A[:,q]) # d = B⁻¹ a_q # --- Step 4: RATIO TEST (choose leaving row p) --- if d ≤ 0 everywhere: return UNBOUNDED p = argmin over {i : d[i] > 0} of x_B[i] / d[i] # --- Step 5: UPDATE --- B = (B \ {p}) ∪ {q} # swap; update B⁻¹ or refactorize update_weights(...) # Devex / steepest-edge recurrence
For four of the five rules the only line that changes is select_entering (and, for the norm-based rules, update_weights); everything else (BTRAN, FTRAN, the ratio test, the basis update) is identical. Greatest increment is the exception: it runs an FTRAN + ratio test inside select_entering for each candidate, which is why it's so much costlier. That near-total modularity is precisely why pivot-rule research can be studied in isolation from the rest of the solver.
11. Nine things to remember
- Revised simplex = simplex reorganized around \(B^{-1}\). Same vertices visited, but quantities computed on demand via BTRAN/FTRAN instead of storing a full tableau.
- Factorize, never invert. BTRAN/FTRAN only solve systems with \(B\), so the solver stores an LU factorization of \(B\) and solves by substitution: sparser, faster, and more numerically stable than an explicit \(B^{-1}\).
- Update, never refactorize from scratch. Consecutive bases differ by exactly one column (a rank-one change), so each pivot just appends an eta vector built from the FTRAN direction \(d\) you already have. Periodically reinvert to reset accumulated cost and error.
- The pivot rule is just the entering-variable policy (Step 2). Everything else in the iteration is fixed linear algebra.
- Dantzig = greediest per-unit rate, cheap but scale-sensitive and exponential in the worst case.
- Greatest increment and steepest edge are easy to confuse, but different: greatest increment maximizes the actual gain \(\bar c_j\cdot t^\star_j\) (rate × feasibility-limited step), steepest edge maximizes the gain per unit distance \(\bar c_j^2/\|d\|^2\) (slope). Greatest increment is the priciest (a ratio test per candidate) and has no cheap approximation, only a Dantzig pre-screen.
- Bland = smallest index; the only one with a hard anti-cycling guarantee, used as a fallback, not a default.
- Devex and steepest edge share one formula \(\bar c_j^2/\gamma_j\); they differ only in whether the edge weight \(\gamma_j\) is approximated cheaply (Devex) or computed exactly via a recurrence (steepest edge). These two dominate modern solvers.
- Dual simplex is primal in mirror order: it holds optimality (dual feasibility) fixed and chases primal feasibility, picking the leaving variable first (most-infeasible \(x_B\)) then the entering one (a ratio test across the pivot row). Its warm-start ability after adding a constraint makes it the default inside MILP solvers.
Math is rendered with MathJax. Key references: Dantzig (1947); Bland, Math. of OR (1977); Harris, Math. Programming (1973, Devex); Goldfarb & Reid, Math. Programming (1977, steepest edge); Lemke (1954, dual simplex); Maros, Computational Techniques of the Simplex Method (2003, bound-flipping / long-step dual); Jeroslow (1973, greatest-increment worst case); Klee & Minty (1972, Dantzig worst case).