## Definition
The **Simplex method** (Dantzig, 1947) is the classic algorithm for [[Linear Programming]]. Walks along edges of the feasibility polytope, vertex to vertex, always moving to an adjacent vertex with better objective value, until no improvement is possible — at which point the current vertex is optimal.
## The Key Insight
For an LP with $m$ constraints in $n$ variables, an optimal vertex of the polytope has at most $m$ non-zero variables. The Simplex method maintains a **basic feasible solution** — a vertex characterised by $m$ "basic" variables — and iteratively pivots to better vertices.
## Algorithm Sketch
```
1. Find an initial basic feasible solution (Phase 1).
2. Phase 2:
while improvement possible:
a. Compute reduced costs for non-basic variables.
b. Pick an entering variable with negative reduced cost (improving direction).
c. Determine leaving variable by minimum-ratio test (maintain feasibility).
d. Pivot: swap entering and leaving variables in the basis.
3. Optimal when no negative reduced cost exists.
```
## Complexity
- **Worst case:** exponential. Klee-Minty (1972) constructed pathological LPs where Simplex visits exponentially many vertices.
- **Average / smoothed case:** polynomial — Spielman & Teng's *smoothed analysis* (2004) proved Simplex is polynomial under random perturbations.
- **Practical:** very fast. Empirically Simplex solves typical LPs in $\sim m$ to $\sim 3m$ iterations.
## Variants
- **Revised Simplex.** Reformulation that avoids storing the full tableau; numerically more stable and faster.
- **Dual Simplex.** Operates on the dual problem; useful for warm-starts after adding constraints.
- **Network Simplex.** Specialised for network-flow LPs; orders of magnitude faster.
- **Cross-over.** Used after interior-point methods to get a basic vertex.
## Simplex vs Interior-Point Methods
For LP:
| | Simplex | Interior-Point |
|---|---|---|
| Worst case | Exponential | Polynomial |
| Practical speed | Very fast on most | Very fast on large |
| Basic vertex solution | Yes (good for warm-start) | No (interior point — needs cross-over) |
| Numerical conditioning | Sensitive | More robust |
In modern LP solvers, both algorithms run; the solver picks whichever wins on the instance.
## When Simplex Wins
- Small-to-medium LPs.
- Mixed-integer programming, where Simplex's warm-start ability is crucial during branch-and-bound iterations.
- Problems where the optimal vertex (sparse solution) is desired.
## When Interior-Point Wins
- Very large LPs (~millions of variables).
- Dense constraint matrices.
## Historical Significance
Simplex was named one of the *Top 10 Algorithms of the 20th Century*. The post-WWII application to logistics, military operations, and economic planning made operations research a discipline.
## Related
- [[Linear Programming]]
- [[Duality]]
- [[Integer Linear Programming]]
- [[Convex Optimization]]