optimization
Feed the army for pennies
It is 1947, and George Dantzig has just formalized linear programming — but there are no computers to speak of, only mechanical calculators and human 'computers.' The test case is the diet problem: choose quantities of seventy-seven foods to meet a dozen nutritional constraints at minimum cost. The naive approach — check every combination — is astronomically infeasible by hand. Solve it exactly with 1947 tools by exploiting the geometry of the feasible region so you visit only the vertices that matter. The method must be mechanical enough to crank through. Get it wrong and either the calculation is intractable and optimization's whole promise stalls, or you settle for a costlier diet than necessary — the simplex idea turned optimization from an art into a procedure a person could execute.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
This is Dantzig's own problem, at his own moment, solved with his own invention. In 1947, as mathematical adviser to the Air Force's SCOOP project, he formalized linear programming and devised the simplex method — the vertex-walking procedure the problem statement describes — precisely so that planning computations could be executed with the era's tools. The diet problem was his proving ground: Stigler had attacked the 77-food, 9-nutrient version heuristically in 1945; Dantzig's group solved it exactly by simplex, a computation famously consuming roughly 120 person-days of clerk labor on desk calculators. Every requirement — exploit polytope geometry, visit only improving vertices, keep the arithmetic mechanical — is a design feature he chose deliberately. The only reason to withhold the last two points is that even Dantzig needed von Neumann's duality insight to complete the theory.
Von Neumann is the second name in this problem's actual history. When Dantzig visited him in fall 1947, von Neumann connected linear programming to his own 1928 minimax theorem within the hour and sketched what became LP duality — the theoretical backbone certifying that a vertex is optimal, which is what lets a hand computation stop with confidence. He was simultaneously the era's deepest thinker about mechanical computation: his 1947 work with Goldstine on the numerical stability of Gaussian elimination analyzes the exact arithmetic simplex pivoting performs, and his Monte Carlo and stored-program work shows total command of what human and machine computers of 1947 could do. He did not invent the pivot procedure, and his instinct ran to theory over clerical craft — the only gaps separating him from Dantzig's score.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
71 figures are scored on this problem. Draw it in a battle to see where you land.