George Dantzig

Life and career

The most famous story about George Dantzig is true, which is unusual for famous stories about mathematicians. As a graduate student at Berkeley in 1939 he arrived late to a class taught by Jerzy Neyman, copied down two problems written on the blackboard, assumed they were homework, and turned them in some days later with an apology for their difficulty. They were open problems in statistical theory. Neyman, some weeks afterward, appeared at Dantzig's door with the news, and the two solutions became his doctoral thesis. The story escaped into folklore, mutated into a motivational parable about the power of not knowing something is impossible, and eventually into the opening scene of a Hollywood film. Dantzig spent decades patiently correcting the embellishments while confirming the core.

He was born in Portland, Oregon, in 1914. His father, Tobias Dantzig, was a Latvian-born mathematician who wrote *Number: The Language of Science*, a book Einstein admired, and who set his son thousands of geometry problems; Dantzig later credited that drilling with giving him whatever analytical power he had. He took a bachelor's degree at Maryland, a master's at Michigan, and then went to Berkeley to work with Neyman.

The war interrupted the doctorate. From 1941 to 1946 Dantzig worked as a civilian in the Army Air Forces' Statistical Control division, in the Combat Analysis Branch, doing the enormous bookkeeping and planning arithmetic that kept an air force supplied and scheduled. This experience is the essential precondition for everything he later did. Military "programming" in that era meant constructing a *program* — a time-phased plan specifying which units did what with which resources on which dates — and it was done by hand, by rooms of people, using rules of thumb. Dantzig came out of the war with a visceral understanding of how large these planning problems were and how badly they needed a mathematical formulation.

He finished the Berkeley doctorate in 1946 and returned to the Pentagon as mathematical adviser to the Air Force Comptroller, on Project SCOOP — Scientific Computation of Optimum Programs. The task was to mechanize planning. In 1947 Dantzig formulated the general linear program: maximize a linear objective subject to linear inequality constraints and nonnegativity. And, crucially, he devised a method to solve it. Rather than search the feasible region, exploit its geometry: the feasible set is a convex polytope, a linear objective attains its optimum at a vertex, so start at a vertex and walk to an adjacent vertex whenever doing so improves the objective. That is the simplex method, designed deliberately so that every step reduced to mechanical arithmetic clerks with desk calculators could execute.

In October 1947 he presented the formulation to von Neumann at Princeton. By Dantzig's own account, von Neumann listened for a few minutes, said something to the effect of *get to the point*, and then delivered an extemporaneous lecture of over an hour on what became the theory of linear programming duality — recognizing immediately that Dantzig's problem was equivalent in structure to the theory of zero-sum games he had built in 1928. That conversation supplied the theoretical half of the subject.

The proving ground was Stigler's diet problem: choose quantities of 77 foods to meet nine nutritional requirements at minimum cost. Stigler had attacked it heuristically in 1945 and got close. Dantzig's group solved it exactly by simplex in 1947 — a computation that consumed something on the order of 120 person-days of hand calculation. Within a few years the same method was running on electronic computers and optimizing oil refinery blends.

Dantzig moved to RAND in 1952, to Berkeley in 1960 where he founded the Operations Research Center, and to Stanford in 1966, where he was professor of operations research and computer science until retirement and where he trained a large share of the field's next generation. He received the National Medal of Science in 1975 and the von Neumann Theory Prize. He continued working on large-scale optimization and on planning under uncertainty for the rest of his life, and died in 2005 at 90.

Key contributions

**Linear programming and the simplex method.** The formulation — $\min c^\top x$ subject to $Ax = b$, $x \ge 0$ — is so canonical now that it takes effort to see it as an invention. The simplex method moves between *basic feasible solutions*, each corresponding to a choice of $m$ basis columns of $A$; at each iteration it computes reduced costs $c_j - c_B^\top B^{-1}A_j$, selects an entering variable with negative reduced cost, performs a ratio test to determine which basic variable leaves without violating feasibility, and pivots. Degeneracy can cause cycling, which is handled by anticycling rules (Bland's rule, lexicographic perturbation). The method is finite and, in practice, spectacularly fast — typically a small multiple of $m$ iterations.

That practical speed is a genuinely deep question rather than a footnote. Klee and Minty showed in 1972 that the standard pivoting rule takes exponentially many steps in the worst case, on a deformed hypercube. Polynomial-time methods came later by different routes — Khachiyan's ellipsoid method in 1979, polynomial but slow in practice, and Karmarkar's interior-point method in 1984, which traverses the interior rather than the boundary and is genuinely competitive. Spielman and Teng's smoothed analysis in 2001 finally explained the gap: simplex runs in expected polynomial time on slightly perturbed instances, so the exponential cases are vanishingly fragile.

**Duality.** Every LP has a dual whose optimal value coincides with the primal's, and whose optimal solution gives the *shadow prices* — the marginal value of relaxing each constraint. Complementary slackness gives a certificate: a pair of feasible primal and dual solutions satisfying it are both optimal, verifiable in a single matrix multiplication. This is what makes LP a tool for economics as well as computation, and its equivalence with von Neumann's minimax theorem is one of the load-bearing facts of the field.

**Large-scale and structured methods.** Dantzig–Wolfe decomposition (with Philip Wolfe, 1960) attacks problems with block-angular structure — many nearly independent subproblems tied by a few coupling constraints — by solving a master problem over columns generated on demand from the subproblems. Column generation, its modern descendant, is how airline crew scheduling and vehicle routing are actually solved. Benders decomposition is the dual analogue. Dantzig also developed generalized upper bounding and the bounded-variable simplex for structured constraint sets.

**Integer programming and cutting planes.** With Fulkerson and Johnson in 1954, Dantzig solved a 49-city travelling salesman instance to proven optimality by formulating it as an integer program, solving the LP relaxation, and adding *cutting planes* — subtour elimination constraints — to remove fractional solutions. This is the origin of the branch-and-cut methodology that every modern MIP solver runs.

**Stochastic programming.** His 1955 work on linear programming under uncertainty introduced two-stage recourse models — decide now, observe the random outcome, then adapt at known recourse cost — which is the foundation of optimization under uncertainty as a discipline.

In battle

Dantzig's profile is a textbook specialist with a wider-than-expected penumbra: 100 problems, mean 35.0, median 30, ten dominant cells and forty at 20 or below.

His categories are led by **games** (72.0 across 3) and **networks** (66.8 across 4) — both artifacts of LP duality reaching into minimax and max-flow — with **optimization** at 56.4 across seventeen problems, his home ground measured over a real problem count, and **experimental-design** at 50.0.

The peak is **P040 — Feed the army for pennies** at 98: his own problem, his own moment, his own invention, docked two points only because completing the theory required von Neumann's duality insight. Around it sit the rest of his empire. **P043 — The assignment in the sky** (96) is the assignment problem, an LP whose constraint matrix is totally unimodular so the LP relaxation is automatically integral. **P178 — The variables that must be whole** (96) is integer programming and cutting planes — the Dantzig–Fulkerson–Johnson method. **P267 — How much can the railway carry?** (95) is max-flow/min-cut, which is LP duality in graph clothing and which Dantzig worked on directly at RAND. **P049 — Schedule the moonshot** (90) is large-scale project scheduling, exactly the SCOOP problem class. **P176 — Cut through the interior** (90) is interior-point methods — not his algorithm, but his problem, and he is scored as the person who defined the object being solved. **P177 — The certificate of optimality** (88) is duality and complementary slackness. **P179 — A good-enough tour of a thousand cities** (85) is large TSP by LP relaxation and cutting planes.

The losses are systematic and worth reading carefully. **Information** (9.0), **regression** (11.5), **computability** (12.0), and **classification** (13.5) are all near the floor: Dantzig's mathematics is deterministic constrained optimization over continuous variables, and it contains no notion of a sampling distribution, an estimator, or an entropy. His floor cells include **P143 — The coefficient that flips sign** (8, multicollinearity), where the issue is statistical identifiability rather than feasibility, and **P284 — Unroll the swiss roll** (8, manifold learning), where the geometry is nonlinear and non-convex in a way his polytopes are not.

Two other floors are the era gap in its purest form: **P248 — The machine that overdosed** (6) and **P249 — The shopping cart that must not vanish** (5) are software-engineering and distributed-systems problems, and his **systems** average of 18.0 across ten problems reflects that he built mathematics, not infrastructure. **P254 — The wall around the data structure** (8) is the same.

The single most instructive number is **P152 — The pixel you cannot see** at 3 — adversarial examples. The matrix's own explanation is careful about it: adversarial attacks *are* optimization problems, and constrained optimization is broadly his subject, but he never worked on non-convex gradient-based attacks or deep-network robustness and the connection is a thin general one. That distinction — being the founder of a field is not the same as having authored a specific method within it decades later — is exactly the discrimination the game is built to teach, and Dantzig is where it shows most cleanly. His **rl** average of 33.7 across eighteen problems is the same story at higher resolution: dynamic programming and policy optimization are optimization, but they are Bellman's, not his.

Play Dantzig anywhere resources are allocated under linear constraints, anywhere duality gives a certificate, and anywhere a large structured planning problem needs decomposing. Avoid him where the world is nonconvex, statistical, or built out of software.