optimization
The variables that must be whole
It is the era when planning problems refuse to bend to continuous math: you cannot build half a warehouse, dispatch a third of a truck, or assign a crew to two-and-a-half flights. The decisions are discrete, and the moment you require variables to be integers the smooth geometry that made linear programming easy shatters — the problem turns NP-hard. Solve it anyway in practice: relax the integrality, solve the easy continuous problem for a bound, branch on a fractional variable and bound each subproblem, pruning whole subtrees that cannot beat the best so far, and tighten with cutting planes. Get it wrong and you brute-force a combinatorial explosion, or round a solution into something infeasible — branch-and-bound is how the discrete decisions of real logistics get made.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
Dantzig is the reason there is a relaxation to solve at all. His 1947 simplex method turned linear programming from a theoretical curiosity into an engine that could plan the Air Force's logistics, and by the 1950s he and colleagues at RAND were already grappling with the integer restriction directly, formulating early cutting-plane ideas for scheduling and assignment problems where fractional trucks and half-built warehouses made no sense. He understood viscerally that the LP relaxation is not the answer but the bound that makes branch-and-bound possible. His simplex tableau is the workhorse inside every node of the search tree this problem describes, and his career-long insistence that optimization serve real logistics makes this his home turf, not a detour.
Karp's 1972 paper 'Reducibility Among Combinatorial Problems' proved that integer programming and its cousins, vertex cover, set packing, the knapsack problem, are NP-complete, giving precise mathematical teeth to the 'shatters' this problem describes. He did not personally write branch-and-bound solvers, but his framework is exactly why the problem needs one: without his reductions there would be no rigorous reason to abandon exact polynomial algorithms and resort to relaxation, branching, and pruning. Berkeley's algorithms culture, which Karp anchored for decades, treated combinatorial optimization as the central battlefield of theoretical computer science. He scores just below Dantzig because his contribution is the hardness proof motivating the method, not the method's engineering. The pruning and bounding vocabulary of modern solvers is essentially an engineering elaboration of the hardness landscape his reductions first mapped out for the field.
Fought here
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.