04 · War and the Science of Search

THE SHORTEST PATH — A History of the Art and Science of Problem-Solving

Portsmouth, 1941

Patrick Blackett had won a Nobel-caliber reputation in physics — he would in fact collect the actual Nobel Prize in 1948, for work on cosmic rays — and in the spring of 1941 he was doing something no physicist had ever been assigned to do before: sitting in a Royal Air Force operations room, watching U-boats sink merchant ships faster than Britain could build them, and trying to compute his way out of it.

The team around him had no official name, so people called it Blackett's circus: a physiologist, a physicist, an astrophysicist, and eventually two future Nobel laureates, all seconded from their laboratories to Coastal Command's new Operational Research Section (INFORMS biographical profile of Blackett). None of them had ever fought a war. What they had was a habit, bred into every physicist, of refusing to trust an intuition that hadn't been checked against a number.

The intuition they checked first nearly ended a career. Britain's convoys — merchant ships sailing in escorted groups across the Atlantic — had for years followed an unspoken rule: keep them small, because a smaller cluster of ships is a smaller target, and fewer eggs are lost if the basket is dropped. Naval officers as senior as America's Admiral Ernest King believed this so firmly that it barely seemed worth testing. Blackett's group tested it anyway, and found the opposite. A U-boat has to find a convoy before it can attack it, and the ocean is enormous; the area available for a submarine to search does not care how many ships are inside a convoy's perimeter. Once a raider does find a convoy, meanwhile, its stock of torpedoes is limited, so a convoy of 80 ships loses only slightly more tonnage to a single attacker than a convoy of 40 — while half as many convoys have to cross the ocean and expose themselves to the risk of being found at all. The reasoning had a clean geometric core: pack merchant ships inside a circle and the number you can fit grows with the area, which scales as the square of the radius, while the escorts patrolling the perimeter only need to scale with the radius itself. Double the convoy's size and you do not need to double its escort — a few more escort ships now guard proportionally far more cargo (Pacific War Encyclopedia, "Convoys"). The British Admiralty had clung to an "ideal" convoy size near 40 ships for no reason anyone could articulate; when it was finally persuaded to run convoys as large as shipping would allow, sinkings fell. Each escort vessel built, the analysts calculated, saved on the order of two merchant ships over the course of the war.

The same circus turned its calculators on the RAF's depth charges — the underwater bombs dropped on submerged U-boats — and found that crews had been fusing them to explode at roughly 100 feet, the depth a submarine commander might plausibly dive to escape. But data on actual attacks showed most U-boats were still near the surface, diving in a panic, when they were caught. Reset the fuse to explode at about 35 feet instead, and a depth charge that used to miss its target because it detonated too deep would now catch boats where they actually were. The change alone is credited with roughly doubling the kill rate of attacks that scored a hit (INFORMS, Blackett profile). Nobody built a new weapon. Nobody found a new tactic. Somebody looked at the numbers already sitting in a filing cabinet and asked a sharper question of them.

This is the discovery this chapter is about, and it is worth stating plainly before the stories pile up: in the crucible of the Second World War, a scattered handful of physicists, statisticians, and economists realized that war — and soon after, business, agriculture, and engineering — was full of decisions that looked like a matter of experience and nerve but were actually optimization problems wearing a uniform. Once you saw them that way, you could solve them with arithmetic instead of instinct. The convoy problem and the depth-charge problem look nothing alike on the surface. Underneath, both are the same move: measure what actually happens, not what you assume happens, and let the measurement — not the veteran's gut — choose the number.

The Bombers That Didn't Come Home

Across the ocean, a mathematician named Abraham Wald was solving a problem with the same shape and a very different flavor, and his name has since attached itself to one of the most retold anecdotes in applied statistics — a story worth telling and worth correcting, because the correction is itself a lesson in this book's thesis.

The version everyone has heard goes like this: the U.S. Army, wanting to armor its bombers without making them too heavy to fly, brought Wald data on where returning aircraft had taken damage — mostly on the fuselage and wings, rarely near the engines — and prepared to reinforce the fuselage. Wald, the story says, told them they had it backwards: armor the engines, because the planes that got hit there were the ones that never made it home to be counted. This is the "survivorship bias" story, and as an illustration of the idea it is close to perfect.

As history, it is largely invented. In 2016 the mathematician Bill Casselman went looking for the primary sources and found astonishingly little: no transcript of Wald delivering advice to a room of generals, no diagram of a bullet-riddled bomber with Wald's own hand on it, nothing resembling the vivid scene retold on a thousand websites. What survives are Wald's actual memoranda for the Statistical Research Group at Columbia, released decades later, and they contain something both less cinematic and more impressive: a technical apparatus for estimating, from the hit patterns on surviving planes alone, the probability that a plane hit n times would have gone down — without ever seeing the missing planes at all (Bill Casselman, "The Legend of Abraham Wald," AMS Feature Column, 2016; the original memoranda and the standard modern gloss are collected in Mangel & Samaniego, "Abraham Wald's Work on Aircraft Survivability," Journal of the American Statistical Association 79 (1984)). Wald assumed enemy fire struck aircraft roughly at random, then built a recursive equation linking the observed distribution of hits on survivors to the unobserved population of planes that never returned — solving, in effect, for the ghosts by their absence from the room. He never records a punchy one-liner about where to bolt the armor; the SRG's stated policy was to answer the technical question it was asked, not to issue tactical advice. The closest primary account, from SRG director W. Allen Wallis, states only that Wald "assumed, on good evidence, that hits in combat were uniformly distributed over the planes" and derived vulnerability estimates from that assumption — the seed, probably, from which the vivid modern retelling eventually grew.

None of this makes the underlying insight less real, or less important to this book. The reframing at the heart of the Wald story — stop treating "the data I have" as "all the data there is," and ask what process filtered the data before it reached you — is exactly the kind of representation change this book is chasing. But the popular version has smoothed a subtle, careful piece of statistical reasoning into a punchy anecdote with a villain (the obtuse generals) and a hero delivering a mic-drop line. The real Wald is more interesting: a mathematician who looked at a table of surviving-aircraft hit-counts and, using nothing but the assumption that bullets don't discriminate, reconstructed a population he could never see. That is a longer path to a shorter insight, and it is the more instructive story of the two.

One Country's Plywood, Another Country's Menu

While Blackett's circus tuned depth charges, a young Leningrad mathematician named Leonid Kantorovich was solving a problem with no evident connection to war at all. In 1938 the local Plywood Trust, a Soviet industrial cooperative, brought him an ordinary-sounding scheduling headache: eight lathes, five kinds of veneer, and a demand to keep the ratio of the five plywood types fixed while maximizing total output. The trust's own engineers had been unable to find a satisfying answer by trial and adjustment.

Kantorovich noticed something that turned out to matter far beyond plywood: the problem was not really about lathes. Any situation where you must allocate a fixed pool of resources among competing uses, subject to a straight-line (linear) relationship between inputs and outputs, has the same skeleton, whatever the resources happen to be — labor hours, tons of steel, hectares of farmland, machine-time. In 1939 he published The Mathematical Method of Production Planning and Organization, showing that an enormous class of allocation problems could be written as one equation: maximize (or minimize) a linear function of many variables, subject to linear constraints (MacTutor History of Mathematics, biography of Kantorovich). He called the technique linear programming before that name existed in the West, and he had no map of how to solve the general version efficiently — only the recognition that the general version existed and that Soviet industry was riddled with disguised copies of it. Decades later, in 1975, he shared the Nobel Memorial Prize in Economic Sciences for exactly this insight (Britannica, "Leonid Vitalyevich Kantorovich") — a Soviet mathematician recognized by a Western economics prize for having spotted, in a plywood factory, the shape of a problem that would eventually run supply chains on both sides of the Iron Curtain.

An ocean away and unaware of Kantorovich's work, the American economist George Stigler ran into the same shape of problem from a completely different door. In 1945 he asked how a moderately active man could eat as cheaply as possible while still meeting the U.S. National Research Council's recommended intake of nine nutrients, choosing freely among 77 available foods. No known method could find the true cheapest diet outright, so Stigler searched by hand among a limited set of promising combinations and reported a diet — wheat flour, evaporated milk, cabbage, spinach, dried navy beans — costing $39.93 per year in 1939 prices (Wikipedia, "Stigler diet"). He knew he had found a good answer, not necessarily the best one, and he said so.

The Method That Ate All the Problems

Two years later, an American mathematician named George Dantzig gave Stigler's diet problem, and every problem shaped like it, a general solution — and the way he arrived there has its own well-documented origin story, separate from the one that would later attach to his name.

Dantzig's simplex method was born of wartime bureaucracy: as a young statistician for the U.S. Army Air Forces, he had grown expert at the mechanics of logistics planning done by hand, on desk calculators, one plan at a time. In June 1947 he formulated a general model for these planning problems as a system of linear inequalities, and by that August had devised the simplex algorithm to solve it — a way of walking, systematically and efficiently, along the edges of the geometric shape formed by a problem's constraints until an optimal corner was reached (George Dantzig, "Origins of the Simplex Method," ACM, 1990; MacTutor biography of Dantzig). Within months, colleagues at RAND had renamed his subject "linear programming," and by 1951 the method was public.

That same fall, a researcher named Jack Laderman at the National Bureau of Standards decided to stress-test the brand-new algorithm on the hardest real instance he could find: Stigler's diet problem, nine nutritional constraints across seventy-seven foods. Using hand-cranked desk calculators — this was still years before general-purpose electronic computers were commonplace — a team spent roughly 120 person-days grinding through the simplex method's arithmetic by hand. The true minimum-cost diet, it turned out, cost only about 24 cents less per year than Stigler's hand-searched estimate (Wikipedia, "Stigler diet"; George Dantzig, INFORMS oral history). Stigler's instincts, honed by an economist's judgment, had gotten within a rounding error of optimal. But the simplex method had gotten there by a procedure, one that would work whether the next problem was a diet, a plywood mill, or a bombing campaign, and would keep working as the number of variables climbed into the thousands, then the millions.

Dantzig's name is also attached to a second, older, and unrelated anecdote, which deserves to be told with its correct date rather than folded into the simplex story: in 1939, as a first-year doctoral student in statistics at Berkeley, Dantzig arrived late to a lecture by Jerzy Neyman and copied down two problems chalked on the blackboard, assuming they were the week's homework. He found them harder than usual but turned in solutions a few days later. They were, in fact, two long-unsolved problems in mathematical statistics, and Dantzig — not knowing this, and so never discouraged from trying — had solved both. The core of the story checks out; the widely circulated embellishments (a ten-problem final exam, a claim that "even Einstein" had failed the problems) do not, and were traced to a later, dramatized retelling by a television preacher rather than to Dantzig himself (Snopes, "The Legend of the 'Unsolvable Math Problem'"). The lesson Dantzig himself drew from it — that not knowing a problem is supposed to be impossible is sometimes the only reason you solve it — belongs to this book's thesis in its own right: the frame around a problem, including the frame of how hard people believe it to be, is part of what makes the space large or small.

A Name to Hide the Math

The most quietly radical idea to come out of the RAND Corporation in this decade belonged to Richard Bellman, and it began, by Bellman's own account, as an act of camouflage.

Bellman arrived at RAND in 1949 already restless in a conventional academic career, and by 1950 was working on what he called multistage decision processes: problems where a sequence of choices, made one at a time, has to add up to a good overall outcome — how to allocate an investment across years, how to route a process through successive stages, how to plan a sequence of moves toward a goal. His key mathematical insight, later formalized as the principle of optimality, is easy to state once seen: an optimal overall plan must also be optimal for every sub-plan it contains, starting from wherever you happen to be partway through. If the last leg of your best possible road trip from Bangkok to Chiang Mai runs through Lampang, then the best route from Lampang onward to Chiang Mai must itself be optimal — because if a better route from Lampang existed, you could substitute it and improve the whole trip. This lets a solver break an enormous multistage problem into a chain of small ones, solved backward from the goal, each one easy once its successor is already known. Bellman called the technique dynamic programming, and the functional equations built on the principle of optimality remain, to this day, one of the handful of general-purpose engines for solving sequential decision problems in economics, engineering, and — chapter 10 will show — reinforcement learning.

The name itself, though, is where Bellman's own account gets interesting to hold up against the calendar. In a 1984 autobiography excerpted by Stuart Dreyfus, Bellman explained that he needed a label that would not sound like "mathematical research," because RAND's ultimate boss at the Department of Defense — a "Secretary Wilson" with, in Bellman's words, "a pathological fear and hatred of the word research" — could not be allowed to suspect he was funding pure mathematics. So Bellman chose programming, a word with an unthreatening, practical ring, and dynamic, an adjective he judged impossible to use pejoratively, and combined them into an umbrella "not even a Congressman could object to" (Stuart Dreyfus, "Richard Bellman on the Birth of Dynamic Programming," Operations Research 50, no. 1 (2002), quoting Bellman's Eye of the Hurricane, 1984). It is a wonderful story about a bureaucrat too literal-minded to tolerate the word "research." There is one problem with the timeline: Bellman's own first published paper using the term "dynamic programming" appeared in the Proceedings of the National Academy of Sciences in August 1952 (Bellman, "On the Theory of Dynamic Programming," PNAS 38, no. 8 (1952)) — while Charles Wilson, the defense secretary Bellman names, did not take that office until January 1953. Bloggers and historians tracking the discrepancy have noted this is at least a year out of order for the story as told (see the discussion at Arcane Sentiment, "Why 'dynamic programming'?"). Bellman may simply have misremembered which official prompted his caution, decades after the fact, or folded two memories into one — autobiographies are not sworn depositions, and his own memoir elsewhere warns, with disarming self-awareness, that "all this contributes to the misleading nature of conventional history." What is not in question is the mathematics: the principle of optimality is real, powerful, and exactly as general as Bellman claimed.

When Searching Is Hopeless, Gamble

Not every wartime problem yielded to an equation. Some problems were so tangled with chance — a neutron careening through a chunk of fissile material, colliding, scattering, occasionally triggering another collision — that no formula could capture their behavior in closed form, and no exhaustive search was remotely possible even for a room-sized calculating machine.

The way out came, by Stanislaw Ulam's own account, from a card game. Recovering from an illness in 1946 and playing endless hands of Canfield solitaire, Ulam found himself wondering what fraction of shuffled decks could actually be won — and realized that after failing to derive the answer by combinatorial analysis, the fastest path to a good estimate was simply to lay out many hands and count. If you cannot calculate the probability of an event from first principles, you can often simulate the event many times and let frequency stand in for probability. Ulam brought the idea to John von Neumann, who saw immediately that the same trick — replace an intractable calculation with a large number of random trials — could model how neutrons diffuse through a bomb core, a problem central to the hydrogen bomb project at Los Alamos. Nicholas Metropolis, working alongside them, gave the resulting family of techniques its lasting name, after the Monaco casino district, in a nod to Ulam's uncle, who reputedly could never resist a trip there (Los Alamos National Laboratory, "Hitting the Jackpot: The Birth of the Monte Carlo Method").

Monte Carlo methods are, in the vocabulary of this book, a confession and a workaround at once: a confession that the space is too large or too tangled to search or compute exactly, and a workaround that trades a guaranteed exact answer for a probable good one, obtained fast. It is the same bet a pollster makes surveying a thousand voters instead of forty million, applied to physics instead of politics — and it would go on to become one of the standard tools of modern computing, invoked whenever a problem's exact structure resists analysis but its outcomes can be cheaply sampled.

One Problem, Many Costumes

Step back from the individual stories and a single, almost eerie pattern comes into view. A team of physicists calculating depth-charge fuses. A statistician reconstructing invisible aircraft losses. A Soviet mathematician scheduling plywood lathes. An American economist pricing a subsistence diet. A young Berkeley graduate student solving problems he didn't know were famous. A RAND consultant hiding calculus inside a politically safe name. A convalescent playing solitaire. None of these people were working on "the same problem" in any sense a layperson would recognize. And yet Kantorovich's lathes, Stigler's groceries, and Dantzig's Army logistics turned out to be one mathematical object — a linear program — in three disguises; Bellman showed that an enormous family of sequential decisions, from investment schedules to shortest routes, share a single recursive skeleton; and Wald's and Ulam's contributions both amount to extracting a signal from a process too large or too obscured to observe directly.

This is the discovery this chapter's decade made, and it is the one that turns problem-solving from a craft into an engineering discipline: the representation is portable. Once you have proven that resource allocation, diet planning, and factory scheduling are the same equation, you do not need a new theory for each one — you need one solver, applied three times. This is also why the unit of optimization stopped being the individual weapon, the individual convoy, or the individual factory line, and became the system: the whole convoy fleet, the whole depth-charge doctrine, the whole supply chain. Optimizing a single ship's speed is a local trick; optimizing the convoy geometry is a system-level insight that saves an ocean's worth of tonnage. The operational researchers of the 1940s were the first people paid, as a full-time job, to ask "what is the actual shape of this problem?" before touching a single lever — and the answer, again and again, was that the shape was smaller and more general than anyone doing the job by feel had ever suspected.

The Move

Move 04 — Optimize the whole system, and measure before you optimize.

• Draw the boundary wide before you draw a single conclusion. Blackett's team did not ask "how do we protect this ship" — they asked "how do we protect this fleet," and the right answer to the wider question (larger convoys) was the opposite of the right answer to the narrower one. Whatever unit you are tempted to optimize — a task, a ship, a plane — ask whether the real unit is one level up.
• Distrust an intuition until you have measured the process that generated your data. Wald's real insight was not a punchline about armor placement; it was refusing to treat "the planes I can see" as "all the planes there are." Before optimizing anything, ask what filtered your sample.
• Look for the linear program, or the recursive equation, hiding inside your problem. Kantorovich's lathes, Stigler's groceries, and Dantzig's logistics were one equation wearing three coats. When a problem feels bespoke, check whether a known general solver already fits it exactly.
• When exact search is hopeless, sample instead of guessing. Ulam's solitaire hands and Metropolis's neutron simulations turned an unanswerable calculation into a countable experiment. A large number of honest trials beats a single confident guess.

Next — Chapter 05 · The Algorithmic Path: the search that operations research did with a slide rule, a new generation would do with a machine — and the first machines that searched would need a theory of their own.