Almost everyone knows one story about George Dantzig, and it is the least interesting true thing about him. A graduate student arrives late, copies two problems off the blackboard thinking they are homework, and solves them; they turn out to be open. The story is real. It is also a distraction, because the thing Dantzig actually did — eight years later, in a Pentagon office, for a problem nobody thought was mathematics — is stranger and far more consequential. He found a way to search a space with astronomically many candidate answers by never entering it. The simplex method walks only the boundary, corner to corner, and it works because of where an optimum is forced to live.
§§1–3 and §7 — Donald J. Albers and Constance Reid, "An Interview with George B. Dantzig," College Mathematics Journal 17:4 (1986), 292–314. Dantzig tells the blackboard story himself there, and it is also where the Wald sequence in §2 is recorded.
§§5–6 — George B. Dantzig, Linear Programming and Extensions (Princeton University Press, 1963), the author's own formal development of the method.
§§6, 8, 9 depend on none of the biography. If every anecdote in this chapter were withdrawn, the mathematics in those three sections would be untouched — which is the correct relationship between a life and a theorem, and the reason they are separated here.
George Bernard Dantzig was a doctoral student at Berkeley, working under Jerzy Neyman — one of the two names on the Neyman–Pearson lemma, and a man with a documented habit of writing unsolved problems on the board without saying so.
Dantzig came in late to a statistics lecture. Two problems were on the blackboard. He copied them down, took them to be the homework assignment, and found them harder than usual. He apologised when he handed them in a few days late.
They were not homework. They were two open problems in mathematical statistics that Neyman had put up as examples of what remained unsolved. Dantzig had solved both. When he needed a thesis, Neyman's advice was, in substance, to put the two papers in a binder and submit them.
The part usually left out is the part worth keeping: Dantzig solved them because he did not know they were hard. He brought to two open problems exactly the effort a competent student brings to an assignment, which is more effort than most people bring to something they have been told is impossible. The information he lacked was not mathematical. It was social.
The problems concerned the existence of certain statistical tests and estimators — the Neyman–Pearson territory of what can and cannot be constructed under constraints on unbiasedness and power. That is the same shape as everything Dantzig later did: given these requirements, does an object satisfying all of them exist, and if so, where is it?
What happened next is better than the legend and is usually cut from it. When Dantzig submitted one of the two solutions for publication, Neyman told him that Abraham Wald had independently reached the same conclusion, in a paper already going to press — "On the Elimination of Unknown Parameters in Problems of Statistical Inference." Neyman's response was to have Dantzig listed as a co-author of Wald's paper, so that the earlier proof was credited.
Note where the initiative sat. Dantzig did not negotiate for it and Wald did not concede it; the senior figure who knew both timelines simply acted. That is the discipline functioning correctly — priority established by who got there, not by who was senior, and arranged by the one person positioned to see both sides.
The blackboard episode escaped into folklore and mutated on the way. It became a motivational sermon illustration in which the student's ignorance is the moral. It became, in outline, the scene in Good Will Hunting where a janitor solves a problem left on a corridor blackboard. It is told with the number of problems varying, the subject varying, and the punchline sharpened.
The mutation is instructive, and it is the same defect this corpus tracks in its own pages: a claim decays in the direction that makes it a better story. Nobody lies. Each retelling improves the anecdote slightly, and after enough retellings the mathematics has dropped out entirely and only the moral remains. Dantzig's own account is duller and better. He worked hard on what he thought was homework, and it took him longer than usual.
The war interrupted the doctorate. Dantzig spent it with the US Army Air Forces in the Office of Statistical Control, doing what would now be called operations research and was then called, without irony, paperwork: how many aircraft, with what crews, carrying what, routed where, supplied by whom, and in what order.
These were not toy questions. A bomber wing's schedule is a system of hard constraints — airframes, trained crew, fuel, ordnance, runway hours, maintenance cycles — with an objective on top of it. The arithmetic was done by hand, by rooms of people, and the plans they produced were feasible but not optimal, because nobody had a method for optimal. They had a method for workable.
The distinction between feasible and optimal is the whole of what came next.
A program, in the military usage Dantzig inherited, was a schedule — a plan of activities over time, with the resources they consume. "Programming" meant producing one. It had nothing to do with computers, which barely existed.
Dantzig's problem was to mechanise it. The Air Force wanted plans generated rather than negotiated, and wanted them to be the best available rather than merely consistent. The obstacle was that no one had written down what "best available" meant in a way a procedure could chase.
What he wrote down was this. Choose non-negative quantities x of each activity, subject to linear resource constraints, maximising a linear objective:
maximise cTx subject to Ax ≤ b, x ≥ 0
Three objects and nothing else: a cost vector, a constraint matrix, a requirements vector. The modelling act — deciding what counts as an activity and which couplings are linear — is where all the judgment lives, and it is done before the mathematics starts.
Tjalling Koopmans is generally credited with suggesting the name linear programming for it, and the name stuck hard enough that when "programming" later came to mean writing code, the older sense survived only here, stranded, in the phrase that made Dantzig's reputation.
The constraints carve out a region of the space of possible plans: every point satisfying all of them at once. Because each constraint is linear, this region is a convex polytope — a solid with flat faces, straight edges and corners, possibly unbounded, possibly empty.
Two facts do all the work.
First: a linear objective on a convex polytope, if it attains a maximum at all, attains it at a vertex. The reason is almost embarrassing once seen. A linear function has no interior peaks — no curvature to hold one. Stand anywhere that is not a corner and there is a direction along which the objective does not decrease; follow it until a wall stops you. Repeat. You arrive at a corner. The entire interior of the feasible region, which is where all the volume is, can be discarded without loss.
Second: the vertices are finite in number, and each is the solution of a square subsystem of the constraints — a choice of which inequalities are tight. So the search is finite, combinatorial, and in principle enumerable.
In principle only. The number of vertices grows combinatorially in the number of constraints and variables; enumeration is hopeless for anything real. Dantzig's contribution is the walk.
Start at a vertex. Examine the edges leaving it. If some edge improves the objective, move along it to the vertex at its far end. Repeat. If no edge improves, stop: the current vertex is optimal, and the fact that no edge improves is itself the proof. The algorithm never enters the interior, never evaluates a point that is not a corner, and terminates with a certificate rather than a confidence.
That last clause is the part that gets least attention and matters most. Simplex does not return a good answer. It returns an answer together with the reason no better one exists, and the reason is checkable independently of the algorithm that produced it. Most of what we now call optimisation returns a number and asks to be trusted.
Dantzig went to Princeton to describe linear programming to John von Neumann. By his own account he had barely begun — a few minutes of exposition — when von Neumann told him to get to the point, and then, having got it, delivered an impromptu lecture of over an hour on the theory of the thing Dantzig had just described.
What von Neumann saw immediately was duality. Every linear program has a shadow — a second program, built from the same data transposed, whose optimum equals the first's. The dual variables price the constraints: each says how much the objective would improve if that particular wall moved outward by one unit. Von Neumann recognised the structure because he had built it already, in the theory of two-person zero-sum games, where the same duality is the minimax theorem.
This is the moment the subject stopped being a scheduling trick and became mathematics. And it is a specific kind of event, worth naming: the recognition that two objects developed for unrelated reasons are the same object. Dantzig had an algorithm for Air Force logistics. Von Neumann had a theorem about poker. They were the same theorem.
For twenty-five years simplex was spectacularly effective and nobody could say why. In 1972, Victor Klee and George Minty settled half the question by constructing a deformed cube — the constraints skewed so that the natural pivoting rule visits every vertex, all 2n of them, before finding the optimum.
So the worst case is exponential. And yet in practice, on problems arising from actual scheduling, simplex takes a number of steps roughly linear in the number of constraints. The Klee–Minty cube is real and essentially never occurs.
That gap stood as an open embarrassment for another thirty years, until Daniel Spielman and Shang-Hua Teng introduced smoothed analysis: instead of asking for the worst case over all inputs, or the average over a distribution nobody believes, ask for the worst case over inputs that have been slightly perturbed. Under that measure simplex is polynomial. The Klee–Minty cube is a knife's edge; jog it and it collapses.
The lesson generalises past this algorithm. A worst-case bound is a statement about an adversary, not about the world. When theory and practice disagree this loudly for this long, the usual fault is in what the theory was asked.
The one way simplex can genuinely fail is subtler than slowness. At a degenerate vertex, more constraints are tight than the dimension requires — three walls meeting along a line in a plane, say. The vertex is one point but corresponds to several distinct choices of tight constraints. The algorithm can pivot from one such description to another, changing its bookkeeping while not moving at all, and in rare cases it can cycle: a closed loop of pivots, objective unchanged, forever.
This is a fold in the exact sense this series uses the word. The map from choices of tight constraints to vertices loses injectivity there — several pre-images, one image — and the pathology is a direct consequence of that loss, not an implementation bug.
Robert Bland gave the clean fix in 1977. Among the candidate pivots, always take the one with the smallest index. It is not the fastest rule; it is the rule that provably cannot cycle, because it imposes a total order that the loop would have to violate. Anti-cycling is a tie-breaking rule — the degeneracy is not removed, only prevented from closing on itself.
In 1975 the Nobel Memorial Prize in Economic Sciences went to Leonid Kantorovich and Tjalling Koopmans, for the theory of optimal allocation of resources. Kantorovich had formulated linear programming problems in the Soviet Union in 1939, independently and earlier, and had been largely unable to get them applied. Koopmans had developed the economics.
Dantzig was not among the laureates. He received the National Medal of Science the same year, and the omission has been remarked on ever since — reportedly including by Koopmans himself. He spent the rest of his career at Stanford, where he had founded the operations research programme, and by all accounts declined to be bitter about it in public.
Two things are true at once and the chapter should hold both. Kantorovich's priority is genuine and was earned under conditions that make it more impressive, not less. And the algorithm that made linear programming a working technology rather than a theory was Dantzig's.
Stated as a structural reading, not a numerical claim. No coefficient of a linear program is asserted to equal any dimensionless constant of this series, and none is fitted to one — the same discipline WP-29 and WP-31 impose everywhere else.
C · Compress. A fleet, a supply chain, a hospital roster — reduced to a matrix, a cost vector and a requirements vector. Everything that is not linear is discarded here, and the discarding is a human judgment made before any mathematics. Most of the failures of applied optimisation are failures of this step, defended afterwards by the rigour of the steps that follow it.
K · Threshold. Each inequality is a wall. The feasible region is where they all hold at once, and the optimum is where some subset of them binds exactly. This is the operator Dantzig is placed under: the method's whole content is the decision to look only where constraints are tight.
F · Fold. Degeneracy. Several descriptions collapsing to one vertex — injectivity lost — with cycling as the visible symptom. Bland's rule does not unfold it; it makes the fold survivable.
U · Unfold. The optimal vertex and its dual certificate, re-entering the world as a schedule someone has to execute and a set of shadow prices telling them which constraint to attack next. The measurement returns to the system it measured.
The placement is worth one caution. The chain is a reading, not a derivation: nothing about the simplex method depends on it, and if the reading were removed the mathematics in §§6–9 would be untouched. It earns its place only if it helps a reader see that a scheduling algorithm and a fold catastrophe have the same skeleton.
Linear programming is now infrastructure. It routes aircraft, blends fuels and animal feed, schedules crews and operating theatres, dispatches electricity across grids, and decides which orders a warehouse fills first. Almost none of it is visible, and almost all of it is running somebody's simplex or interior-point solver right now.
Which makes the modelling step — the compression — a moral act, and this is where the chapter meets WP-27's Ethics of Algebra. Correctly done mathematics has no ethics of its own; the ethics live in who decides what goes in the matrix and to whom the objective belongs. An LP that schedules nurses will produce an optimal roster with respect to whatever was written in c. If nobody put fatigue in the objective, the optimum will be brutal, and it will be provably optimal, and the proof will be correct.
Dantzig's own famous first application makes the point better than argument. The diet problem — minimise the cost of a diet meeting nutritional requirements — was one of the earliest large linear programs solved. The mathematics was flawless. The answer was a diet no human being would eat, because palatability was not a constraint and nobody had thought to make it one.
The feasible region contains only what you put in it. That is the whole warning, and it was visible in the first serious application, in the first decade.
He is remembered for arriving late to a lecture. He should be remembered for noticing that if you are looking for the best point in a convex region, you can throw away the entire inside of it — and that the reason you can is that a flat objective has nowhere to rest except against a wall.