The Simplex Method

In 1947, George Dantzig invented an algorithm that would quietly run inside airlines, oil refineries, logistics networks, and financial models for the rest of the century — and still does. He called it the simplex method.

The problem it solves is called linear programming: maximize (or minimize) a linear objective function subject to a set of linear inequality constraints. Picture a factory deciding how many units of two products to make, constrained by limited labour and materials, trying to maximize profit. Every constraint carves away a half-space; what remains is a convex polytope — the feasible region. The optimum, if one exists, always sits at a corner (vertex) of that polytope.

Simplex exploits this: start at any corner, check whether any neighboring corner improves the objective, and pivot to the better one. Repeat until no neighbor is better — that corner is the global optimum. The logic is clean because linear functions are convex: there are no local optima to trap you.

What makes this story interesting for complexity theory is the gap between theory and practice. In the worst case, simplex visits an exponential number of corners (Klee and Minty proved this in 1972). Yet on real-world instances it typically takes only $O(m)$ pivots for a problem with m constraints — a number that barely grows with problem size. Understanding why is one of the open questions in the field.

Below is a small 2D linear program: maximize 3x + 2y subject to four inequality constraints. The shaded region is the feasible polytope; the labeled points are its corners (vertices). Each corner has a value of the objective 3x + 2y shown beside it.

Click Next Pivot to let simplex walk from one corner to a better neighbor, one step at a time. The algorithm always moves uphill — toward a higher objective value. Click Reset to start again from a different corner.

<div class="lp-header">
  <div class="lp-info">
    <span class="lp-label">{{maximize}}</span>
    <span class="lp-obj" id="obj-display">3x + 2y</span>
  </div>
  <div class="lp-constraints">
    <span class="lp-label">{{subject_to}}</span>
    <span>x ≤ 6 &nbsp;|&nbsp; y ≤ 5 &nbsp;|&nbsp; x + y ≤ 9 &nbsp;|&nbsp; x,y ≥ 0</span>
  </div>
</div>
<canvas id="lp-canvas" width="340" height="300"></canvas>
<div class="lp-status">
  <div class="status-row">
    <span class="status-label">{{current_vertex}}</span>
    <span id="vertex-label" class="vertex-val">—</span>
  </div>
  <div class="status-row">
    <span class="status-label">{{objective_value}}</span>
    <span id="obj-val" class="obj-val">—</span>
  </div>
  <div id="msg" class="msg"></div>
</div>
<div class="btns">
  <button id="btn-pivot" type="button">{{next_pivot}}</button>
  <button id="btn-reset" type="button" class="ghost">{{reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.lp-header { background: #eef2f7; border-radius: 8px; padding: .55rem .8rem; margin-bottom: .5rem; font-size: .88rem; line-height: 1.7; }
.lp-label { font-weight: 700; margin-right: .3rem; color: #1d3557; }
.lp-obj { font-family: ui-monospace, monospace; color: #1d3557; font-weight: 600; }
.lp-constraints { color: #444; }
#lp-canvas { display: block; border-radius: 10px; background: #f8fafc; border: 1px solid #dde4ec; max-width: 100%; }
.lp-status { display: flex; flex-direction: column; gap: .2rem; margin: .55rem 0; font-size: .93rem; }
.status-row { display: flex; align-items: center; gap: .4rem; }
.status-label { color: #555; font-size: .86rem; }
.vertex-val { font-family: ui-monospace, monospace; font-weight: 700; color: #1d3557; font-size: 1rem; }
.obj-val { font-family: ui-monospace, monospace; font-weight: 700; color: #e63946; font-size: 1rem; }
.msg { font-size: .9rem; font-weight: 600; min-height: 1.3em; color: #0a7d33; }
.msg.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice: the path is short and direct. Even if you pick the worst starting corner, simplex finds the optimum in just a few pivots on this small example. On a 2D polytope with 4 constraints there are at most 4 corners — trivial. Scale up to millions of variables and millions of constraints, and the question of how many pivots are needed becomes profound.

The complexity story of linear programming is one of the most instructive in all of algorithms:

• Easy to verify: given a candidate corner and a claimed objective value, checking optimality is fast — just confirm no constraint is violated and no neighbor improves the objective.
• Worst-case exponential: Klee and Minty (1972) constructed a family of LP instances where simplex (with the standard most-negative-coefficient pivot rule) visits every corner of the polytope before finding the optimum. With n variables their example has $2^{n}$ corners.
• Polynomial in theory: in 1979, Leonid Khachiyan proved that the ellipsoid method solves LP in polynomial time — the first theoretical breakthrough. In 1984, Narendra Karmarkar gave a practical polynomial algorithm: interior-point methods, which travel through the inside of the polytope rather than along its edges.
• Simplex in practice: despite the worst case, simplex remains the dominant solver. On typical real-world instances it performs in roughly $O(m)$ to $O(m \log m)$ pivots — nobody has proved why. Average-case analyses (Spielman & Teng's smoothed complexity, 2004) show that tiny random perturbations of inputs guarantee polynomial expected pivots, capturing why pathological inputs almost never appear in practice.
• Open question: is there a pivot rule that makes simplex provably polynomial for all inputs? This is connected to the Hirsch conjecture (disproved in 2010 by Santos, but the polynomial diameter question remains open) and to deep questions about the geometry of polytopes.

Linear programming itself sits in P thanks to interior-point methods. But the simplex method — still the workhorse of optimization — is an everyday reminder that worst-case complexity and practical behavior can diverge dramatically. This gap also shows up in integer programming, where adding integrality constraints makes the problem NP-hard.

Linear programming, and simplex as its main engine, sits at the core of modern optimization:

• Airline operations: crew scheduling and seat pricing are LP sub-problems solved millions of times per day. A 1% improvement in fuel allocation alone saves tens of millions of dollars annually.
• Supply chain and logistics: routing, warehouse assignment, and production planning are LP or mixed-integer programs; simplex runs inside every major ERP system.
• Portfolio optimization: Markowitz mean-variance optimization is a quadratic program whose linear relaxation is solved by simplex as a subroutine.
• Machine learning: support vector machines (SVMs) reduce to a quadratic program; the training of large linear models uses LP duality extensively.
• Network flow and telecommunications: max-flow and min-cost-flow problems are LP instances where the constraint matrix is totally unimodular — making integer solutions automatic, and simplex the perfect solver.
• Energy and infrastructure: power grid dispatch, refinery blending, and water-network flow all run as LP models that simplex solves in real time.

Understanding simplex means understanding linear programming — the backbone of operations research — and its relationship to the harder world of integer programming, where integrality makes problems NP-complete.

The simplex method is a paradox made practical. Theory says it can take exponentially many steps; practice says it almost never does. Klee and Minty found the booby-trapped polytope; real industrial problems never look like that. Interior-point methods give us the polynomial guarantee we craved, but simplex runs the world's LP solvers anyway — faster on average, better in warm-start scenarios, and deeply integrated into the integer-programming branch-and-bound engines that solve the hardest scheduling and routing problems.

The lesson is broader than optimization. When you study an algorithm's complexity, the worst case is only part of the story. Average-case behavior, smoothed complexity, and the structure of real inputs all matter. Simplex found the optimum long before anyone could explain theoretically why it was allowed to.

If you want to go deeper, see how adding integrality constraints turns LP into integer programming — and sends it from P straight into NP-hard territory.