George Dantzig and the Simplex Method
Abstract
George Dantzig (1914–2005) invented linear programming’s simplex method in 1947 and, with it, the field of mathematical optimization as an industrial practice, the machinery that decides which planes fly which routes, what refineries brew, how supply chains route goods, and how portfolios are balanced. He is also the true origin of one of the most retold stories in mathematics: the graduate student who arrived late to class, mistook two famous unsolved problems on the blackboard for homework, and solved them both. Unlike most legends, this one is documented, and its garbled retellings eventually became the premise of Good Will Hunting.
The Homework That Wasn’t
Dantzig (born in Portland, Oregon in 1914, son of the mathematician Tobias Dantzig and named after George Bernard Shaw) entered the doctoral program at UC Berkeley in 1939 to study statistics under Jerzy Neyman. One day he arrived late to Neyman’s class and found two problems on the blackboard. He copied them down, assuming they were the week’s homework, and handed in solutions a few days later, apologizing that they had “seemed a little harder than usual.”
They were not homework. They were two famous unsolved problems in mathematical statistics that Neyman had presented as examples. Weeks later Neyman turned up at Dantzig’s door with the news; when Dantzig later worried about a thesis topic, Neyman told him to put the two solutions in a binder and he would accept them as his dissertation. Dantzig told the story himself, most fully in a 1986 College Mathematics Journal interview.
The Legend Escapes Its Owner
The story spread, first as a motivational sermon illustration (Dantzig had told it to a minister, and it entered the folklore of positive thinking: he solved them because no one told him they were unsolvable), then in mutated versions attributed to Einstein or to anonymous students. Snopes rates the core story true, correctly attributed to Dantzig. Screenwriters have acknowledged the anecdote’s shadow in Good Will Hunting (1997), whose opening (a janitor casually solving a problem left on an MIT blackboard) is the legend’s Hollywood form. Dantzig thus occupies a rare position: a real mathematician whose true story became an urban legend that became a movie.
Programming Before Programming
During World War II, Dantzig led the Combat Analysis Branch of the Air Force’s Statistical Control division, where “programs” meant plans, schedules of training, supply, and deployment. Asked after the war to mechanize this planning, Dantzig posed the general problem in 1947: optimize a linear objective subject to linear inequality constraints. He then invented the simplex method, walk along the vertices of the feasible region’s polytope, always improving, until no improvement is possible.
The name “linear programming” thus has nothing to do with computer code: the “programming” is the military planning sense (economist Tjalling Koopmans suggested the final phrasing). The field’s later vocabulary (including Bellman’s “dynamic programming”) inherited the same pre-software meaning of “program.”
In 1947 Dantzig presented the framework to John von Neumann, who (in a display that became part of optimization folklore) immediately connected it to his game theory and sketched what became duality theory on the spot. An early demonstration solved Stigler’s “diet problem” (cheapest diet meeting nutritional requirements): 9 constraints in 77 unknowns took nine clerks with desk calculators about 120 person-days. The exercise made the point precisely: the mathematics worked, and only the coming electronic computer could make it routine.
The Invisible Infrastructure of Decisions
The simplex method arrived at the same moment as the stored-program computer, and the two grew together. Linear programming became (and remains) one of the largest consumers of computing cycles in industry:
- Airlines assign fleets and crews with it; a major carrier’s crew-scheduling LP has millions of variables.
- Refineries and power grids dispatch production by LP every day; commodity and electricity prices are literally shadow prices from these models.
- Logistics (from wartime convoys to container shipping to same-day delivery) is LP and its integer-programming extensions.
- The diet problem returned as agribusiness feed formulation, solved millions of times a year.
Theory added a twist: in 1972 Klee and Minty showed the simplex method can take exponential time in the worst case, and in 1979–84 Khachiyan’s ellipsoid method and Karmarkar’s interior-point method achieved polynomial bounds, yet on real problems, simplex remains stubbornly, unreasonably fast, a standing puzzle that later “smoothed analysis” (Spielman and Teng’s 2004 paper, which won the 2008 Gödel Prize) went a long way toward explaining. The episode is a textbook case in why worst-case complexity (P vs. NP) and practical performance are different sciences.
Dantzig received the National Medal of Science in 1975; the great puzzlement of his admirers is that the Nobel Memorial Prize in Economics went to Koopmans and Kantorovich in 1975 for linear programming while passing over the man who made it computable. He spent his later career at Stanford and died on May 13, 2005.