Simplex Method

The linear-programming problem

A linear program (LP) in standard form asks for the values of n real variables x = (x₁, …, x_n) that maximise a linear objective subject to linear inequality constraints:

maximise   c · x
subject to A x ≤ b
           x ≥ 0

Here c is an n-vector of profit coefficients, A is an m × n matrix of constraint coefficients, and b is an m-vector of right-hand sides. Every constraint is a half-space; their intersection (along with the non-negativity orthant) is the feasible region, a convex polytope. The objective c · x is linear, so its level sets are parallel hyperplanes. Optimising means sliding the level set as far as it goes in the direction of c without leaving the polytope. The level set first separates from the polytope at a vertex.

That single geometric fact — that an LP optimum always sits at a vertex — is what makes the simplex method work. Instead of searching all of ℝⁿ, you only need to enumerate the polytope's vertices. There may be many of them (combinatorially as many as C(m+n, n)), but the simplex method visits only a tiny fraction.

Dantzig and the warroom

George Dantzig developed the algorithm in 1947 while working as a mathematical adviser to the US Air Force on what they called programming: the scheduling of training, deployment and supply across thousands of bases. The name linear programming originally meant linear scheduling, not the modern sense of computer programming — Dantzig later joked that he chose the term partly because program sounded sufficiently buzzwordy in 1947 Washington to attract budget.

The first published account of the simplex method appeared in 1951 in Activity Analysis of Production and Allocation, edited by Tjalling Koopmans. By the late 1950s the method was running daily on early IBM mainframes for refineries, steel mills, and the United States Air Force's MILSTAMP supply network. Dantzig's 1963 textbook Linear Programming and Extensions remains a standard reference.

The algorithm in five lines

1. Convert to standard form. Add a slack variable s_i to each inequality so Ax + s = b with x, s ≥ 0. Now everything is an equality plus non-negativity.
2. Find an initial basic feasible solution. One vertex of the feasible polytope. Often the origin x = 0, s = b works if b ≥ 0; otherwise run Phase I, a small auxiliary LP, to find one.
3. Compute reduced costs. For every non-basic variable, compute the change in the objective per unit increase. If all reduced costs are non-positive, the current vertex is optimal — stop.
4. Pivot. Pick a non-basic variable with positive reduced cost (the entering variable). Increase it until some basic variable hits zero (the leaving variable). Swap them. The new basis describes a neighbouring vertex with a strictly better objective.
5. Repeat from step 3.

That is the entire skeleton. Implementing it efficiently means storing the basis matrix in factored form, rebuilding the factorisation when it gets numerically dirty, and choosing pivot rules that converge fast. Modern revised simplex implementations exploit sparsity heavily — most large LPs have constraint matrices in which 99% of entries are zero.

Worked example: a tiny production LP

Suppose a workshop makes two products. Product A yields $3 profit per unit, B yields $2. Manufacturing uses two resources. Labour: 1 hour per A and 1 hour per B, with 4 hours available. Material: 2 kg per A and 1 kg per B, with 6 kg available. Both quantities must be non-negative. Solve:

maximise   3 x + 2 y
subject to    x +   y ≤ 4   (labour)
            2 x +   y ≤ 6   (material)
                x, y ≥ 0

Adding slacks s₁, s₂:

x + y + s₁         = 4
2x + y      + s₂   = 6
x, y, s₁, s₂ ≥ 0
objective z = 3x + 2y

Start at the origin: x = y = 0, s₁ = 4, s₂ = 6, z = 0. The basic variables are {s₁, s₂}; the non-basic ones are {x, y}. Reduced costs: ∂z/∂x = +3, ∂z/∂y = +2. Both positive — the origin is not optimal.

Iteration 1. x has the largest reduced cost, so it enters. Increase x while keeping y = 0. Labour says x ≤ 4; material says 2x ≤ 6, so x ≤ 3. Material is the binding constraint, so s₂ leaves. Pivot:

New basis: {x, s₁}.
From row 2: x = 3 - 0.5 y - 0.5 s₂
Sub into row 1: s₁ = 4 - x - y = 1 - 0.5 y + 0.5 s₂
Sub into z:    z = 3 x + 2 y = 9 + 0.5 y - 1.5 s₂

Vertex: x = 3, y = 0, s₁ = 1, s₂ = 0   →   z = 9

Iteration 2. Reduced costs in the new basis: ∂z/∂y = +0.5, ∂z/∂s₂ = −1.5. y is still positive, so y enters. The constraint on y is s₁ ≥ 0, i.e. 1 − 0.5 y ≥ 0, so y ≤ 2. s₁ leaves. Pivot:

New basis: {x, y}.
From the row 1 update: y = 2 + s₂ - 2 s₁
From the row 2 update: x = 3 - 0.5 y - 0.5 s₂ = 2 - s₂ + s₁
Sub into z:           z = 10 - s₁ - s₂

Vertex: x = 2, y = 2, s₁ = 0, s₂ = 0   →   z = 10

Iteration 3. Both remaining reduced costs are negative (−1, −1), so increasing any non-basic variable would lower the objective. The current vertex is optimal. The workshop should make 2 of A and 2 of B, earning $10. The labour and material are both fully consumed (s₁ = s₂ = 0).

Three pivots, three vertices, terminated at the optimum. On a problem with only two real variables you can also see the answer geometrically: the feasible region is a quadrilateral with vertices (0,0), (3,0), (2,2), (0,4); evaluating z = 3x + 2y at each gives 0, 9, 10, 8 respectively. The simplex method visited (0,0) → (3,0) → (2,2) and stopped.

Algorithmic comparison

	Simplex method	Ellipsoid (Khachiyan 1979)	Interior-point (Karmarkar 1984)
Complexity	Exponential worst case	Polynomial O(n⁶ L)	Polynomial O(n^3.5 L)
Practical speed	Very fast on average	Very slow in practice	Fast on huge LPs
Strategy	Walk vertices on boundary	Shrinking ellipsoids	Cut through the interior
Iteration count	2–3 (m+n) typically	Polynomial but huge	50–100 typically
Iteration cost	Cheap pivot	Expensive ellipsoid update	One sparse Newton solve
Warm starts	Excellent (LP after edit)	Poor	Poor
Used inside	Branch-and-bound for IP	Theoretical proofs only	Large-scale convex/SDP

The right-hand columns explain why simplex did not get retired when interior-point methods proved polynomial. Branch-and-bound for integer programming repeatedly solves LPs that differ by one constraint; simplex restarts from the previous vertex almost for free, while interior-point methods have to redo most of the work. Most production solvers ship both algorithms and pick automatically.

Where the simplex method shows up

• Airline crew scheduling. Delta Air Lines schedules around 28,000 pilots and flight attendants daily by solving LP relaxations inside a column-generation solver, with the simplex method as the inner workhorse. The LP master problem can have millions of columns generated on the fly.
• Refinery blending. Shell, BP and ExxonMobil blend crude streams into gasoline grades by solving LPs every few hours: maximise margin subject to octane, sulphur, vapour pressure, and demand constraints. A typical blend LP has ~10,000 variables and solves in seconds.
• Electricity unit commitment. Independent system operators (PJM, ERCOT, MISO) clear day-ahead and real-time energy markets by solving mixed-integer LPs over thousands of generators. The continuous relaxation is the simplex method's home turf; integer commitment decisions are wrapped in branch-and-bound.
• Sports league scheduling. Major League Baseball's 2,430-game season is generated by a custom integer program. The Sports Scheduling Group (Trick et al.) reportedly uses simplex inside CPLEX with thousands of variables and constraints for divisional balance, travel, broadcast windows and rest rules.
• Quantitative portfolio optimisation. Mean-variance optimisation is quadratic, but linear constraints (sector limits, turnover bounds, position caps) are usually handled by simplex-style pivoting inside QP solvers. Most quant funds run thousands of LP-flavoured optimisations per trading day.

Variants and extensions

• Revised simplex. Stores the inverse of the basis matrix in factored form (LU + Bartels-Golub updates) instead of keeping a full tableau. Standard for any LP with more than a few hundred variables — the only practical version on real industrial problems.
• Dual simplex. Maintains dual feasibility and works toward primal feasibility, the reverse of the standard primal simplex. Crucial for warm-starting after a constraint is added in branch-and-bound.
• Network simplex. A specialisation for min-cost flow problems where the basis is a spanning tree of the network. Each pivot is O(m) in the network size, giving extremely fast solves for transportation, assignment and shortest-path problems.
• Bland's rule and the lexicographic method. Anti-cycling rules that guarantee finite termination at the cost of slower per-iteration progress. Used as fallbacks when degeneracy is detected.
• Branch-and-cut for integer programming. Repeatedly solves LP relaxations using simplex, then adds cutting planes to tighten the polytope. The combination is what powers commercial solvers like CPLEX, Gurobi and the open-source HiGHS.

Common pitfalls

• Ignoring degeneracy. When more than the minimum number of constraints meet at a vertex, the simplex can pivot without changing the objective — and in pathological cases cycle forever. Detect cycling and switch to Bland's rule, or use a perturbation method.
• Bad scaling. If some constraint coefficients are 10⁻⁶ and others are 10⁶, the LU factorisation of the basis goes numerically unstable. Always scale rows and columns to roughly unit magnitude before solving.
• Treating an unbounded LP as infeasible. If a non-basic variable can be increased indefinitely without violating any constraint, the LP has no maximum — the simplex method should report unbounded, not just fail. Many homemade implementations confuse the two states.
• Forgetting to verify Phase I succeeded. If the auxiliary problem in Phase I terminates with a non-zero artificial variable in the basis, the original LP is infeasible. Skipping that check leads to silently wrong answers.
• Treating the simplex method as a black box for integer programs. Solving the LP relaxation gives fractional answers; rounding them is almost always wrong. Integer programs need branch-and-bound, branch-and-cut, or a constraint-programming layer on top.

Why the simplex method is still everywhere

By any measure of decades-of-industrial-runtime, the simplex method is the most-used optimisation algorithm ever written. Its theoretical complexity is bad — Klee and Minty's 1972 cube provably forces exponentially many pivots — but no real industrial LP looks like the Klee-Minty cube. Spielman and Teng's 2001 smoothed analysis proved that under any small random perturbation of the data, the expected pivot count is polynomial. This matches eighty years of practice: real LPs solve in dozens to hundreds of pivots, never in the worst-case millions.

The simplex method's other irreplaceable feature is its warm start: after solving an LP, you can change a constraint, add a column, or branch on a variable, and the algorithm picks up from the previous vertex with usually only a handful of additional pivots. Interior-point methods have to redo the whole calculation. That single property is why every branch-and-bound solver, every column-generation pipeline, every portfolio rebalancer is still built on top of simplex eighty years after Dantzig's first run.