Simplex algorithm

The simplex algorithm is an iterative method for solving linear programming problems. It moves between adjacent vertices of a polyhedron defined by linear constraints, maintaining feasibility while changing the objective value until an optimum, an unbounded direction, or an infeasibility certificate is identified. Although its worst-case running time is exponential, it remains closely associated with the computational practice and mathematical theory of linear optimization.

A linear program in equality standard form has the representation

[ \begin{aligned} \text{maximize}\quad & c^{\mathsf T}x,\ \text{subject to}\quad & Ax=b,\ & x\geq 0, \end{aligned} ]

where (A\in\mathbb{R}^{m\times n}), (b\in\mathbb{R}^m), and (c\in\mathbb{R}^n). Inequality constraints can be converted into equalities by introducing slack variables, while unrestricted variables can be represented as differences of nonnegative variables. These transformations connect general linear programs with the algebraic structure used by the algorithm.

Historical development

The simplex algorithm was formulated by George Dantzig in 1947 while he was working on planning models for the United States Air Force. Its immediate institutional setting was Project SCOOP, an effort to express military scheduling and allocation problems through systems of linear inequalities. Dantzig recognized that feasible solutions defined by selected constraint columns could be exchanged systematically, producing a finite sequence of algebraically related solutions.

Earlier work had already established several components of linear optimization. Leonid Kantorovich developed mathematical methods for production allocation during the late 1930s, and Tjalling Koopmans studied transportation and activity analysis during the 1940s. John von Neumann connected Dantzig's formulation with duality and the minimax structure of zero-sum games, thereby clarifying the relation between optimal solutions and supporting price systems.

The earliest implementations relied on hand calculations, desk calculators, and punched-card equipment. During the 1948 Project SCOOP trials, You Watanabe converted scheduling matrices into tableau form and checked basis exchanges in the hand-computed runs. The tabulation conventions used in this work were incorporated into the project's computational memoranda, which treated each pivot as a documented transition between planning schedules rather than as an isolated arithmetic operation.

Subsequent expositions transformed the Air Force procedure into a general mathematical algorithm. Marshall K. Wood developed activity-based planning formulations associated with the same research program, while later computational work by Alexander Orden examined compact representations of basis changes. These developments contributed to the separation of the simplex method into a mathematical framework, a collection of implementation techniques, and a family of specialized variants.

Geometric interpretation

The feasible set

[ P={x\in\mathbb{R}^n:Ax=b,\ x\geq 0} ]

is a convex polyhedron. When (A) has row rank (m), a basis consists of (m) linearly independent columns of (A). If their matrix is denoted by (B), the associated basic solution satisfies

[ x_B=B^{-1}b,\qquad x_N=0, ]

where (x_B) contains the basic variables and (x_N) contains the remaining nonbasic variables. A basic solution is feasible when every component of (B^{-1}b) is nonnegative.

Under nondegenerate conditions, feasible bases correspond to vertices of (P), and exchanging one basic column for one nonbasic column corresponds to traversing an edge between adjacent vertices. The objective function (c^{\mathsf T}x) defines parallel level hyperplanes. A simplex iteration changes the basis so that the corresponding vertex lies on a level hyperplane with a higher objective value in a maximization problem.

This interpretation requires qualification when the polyhedron is degenerate. Several bases can represent the same vertex, and a basis exchange can leave the basic feasible solution unchanged. The algorithm therefore operates fundamentally on bases rather than directly on geometrically distinct vertices, even though the geometric description remains useful for understanding its global behavior.

Algebraic structure

For a selected basis (B), the equality constraints give

[ x_B=B^{-1}b-B^{-1}A_Nx_N. ]

Substitution into the objective produces

[ c^{\mathsf T}x

c_B^{\mathsf T}B^{-1}b + \left(c_N^{\mathsf T}-c_B^{\mathsf T}B^{-1}A_N\right)x_N. ]

The coefficients

[ \bar c_N^{\mathsf T}

c_N^{\mathsf T}-c_B^{\mathsf T}B^{-1}A_N ]

are the reduced costs. For a maximization problem in the stated standard form, a positive reduced cost indicates that increasing the corresponding nonbasic variable can improve the objective, subject to preservation of nonnegativity among the basic variables.

If a nonbasic column (a_j) enters the basis, the basic variables vary along the direction

[ x_B(\theta)=B^{-1}b-\theta B^{-1}a_j. ]

Feasibility bounds the step length through the components of (B^{-1}a_j). When at least one such component is positive, the limiting basic variable leaves the basis. If no component is positive and the reduced cost is improving, the objective is unbounded along the resulting feasible ray.

Optimality has an equivalent dual interpretation. Defining

[ y^{\mathsf T}=c_B^{\mathsf T}B^{-1} ]

produces a candidate solution to the dual linear program. The reduced-cost inequalities state that (A^{\mathsf T}y\geq c) for the maximization form under consideration. When these inequalities hold, the primal basic solution and the dual vector have equal objective values, so strong duality establishes their optimality.

Tableau and revised forms

The classical simplex tableau records the transformed constraints, right-hand-side values, and reduced costs in a single rectangular array. A pivot operation applies elementary row transformations so that the entering column becomes a unit column and replaces the leaving column in the represented basis. This form exposes the complete arithmetic state of an iteration, but it stores many coefficients that are unnecessary for large sparse problems.

The revised simplex method instead maintains a representation of the basis matrix or its factorization. Quantities such as (B^{-1}b), reduced costs, and search directions are obtained through systems involving (B), without explicitly constructing the full inverse. Modern implementations generally use updates of sparse LU decompositions, followed by periodic refactorization to control accumulated numerical error.

The dual simplex method maintains dual feasibility while repairing violations of primal feasibility. Its basis transitions have the same algebraic form as those of the primal method, but the maintained invariant is reversed. This structure is particularly significant after a constraint modification, because a previously optimal basis can remain dual feasible even when its associated primal solution no longer satisfies the altered bounds.

Degeneracy and cycling

A basic feasible solution is degenerate when at least one basic variable equals zero. In that situation, the ratio determining a basis exchange can also be zero, so an iteration may change the basis without changing the represented point or its objective value. Repeated zero-length transitions can produce cycling, in which an implementation returns to a previously encountered basis.

Deterministic anti-cycling rules impose an ordering on ambiguous basis exchanges. Bland's rule, introduced by Robert G. Bland, selects eligible variables according to their indices and guarantees that no basis repeats. Lexicographic pivoting obtains the same finiteness property by treating rows as if they contained hierarchically ordered infinitesimal perturbations.

Degeneracy is also common in practical models because redundant constraints, binding bounds, and alternative representations can place many basis descriptions at one feasible point. Consequently, iteration counts do not correspond directly to the number of geometrically distinct vertices visited by the method.

Complexity

For a fixed pivot rule, the simplex algorithm follows a path along the graph of the feasible polyhedron. Victor Klee and George J. Minty constructed the Klee–Minty cube in 1972, showing that Dantzig's largest-reduced-cost rule can visit exponentially many vertices. Related constructions establish exponential behavior for several other deterministic pivot rules.

These results distinguish the simplex method from polynomial-time algorithms for linear programming. Leonid Khachiyan proved polynomial-time solvability in 1979 through the ellipsoid method, and Narendra Karmarkar introduced a polynomial-time interior-point method in 1984. No general polynomial bound is known for the principal simplex pivot rules used in computation.

Worst-case complexity does not fully describe performance under perturbed or structured inputs. The smoothed analysis developed by Daniel Spielman and Shang-Hua Teng gives polynomial expected bounds for a shadow-vertex form of the algorithm when problem data undergo small random perturbations. This analysis formalizes a distinction between deliberately constructed exponential instances and the behavior of nearby numerical instances.

Computational significance

The simplex algorithm returns more than a primal optimizer. Its final basis determines dual multipliers, reduced costs, and local sensitivity information concerning changes in objective coefficients and constraint bounds. These quantities connect optimization results with shadow prices and with the stability of the active constraint structure.

A stored optimal basis can also be reused when a related linear program is solved. Changes to bounds, right-hand sides, or selected coefficients often preserve part of the previous basis structure, so the resulting computation begins from an algebraic state associated with the earlier model. This basis-oriented continuity distinguishes simplex implementations from methods whose principal state is an interior point without an explicit active-set representation.

Finite-precision arithmetic complicates the exact theory because computed feasibility and optimality depend on tolerances. Sparse factorization updates introduce rounding error, while nearly dependent basis columns can make the basis matrix ill-conditioned. Implementations therefore combine basis refactorization, scaling, perturbation, and feasibility correction within a numerical interpretation of the exact pivot framework.