The Last Place "Optimal" Means Anything

"OPTIMIZE" is the motto of our age. Everyone is an optimiser now. Sleep, morning routines, tax, protein intake, the loading order of a web page. The word has been worn down until it means roughly better than what I was doing last month, which is something you feel rather than something you check.

All is not lost, dear reader. One discipline kept the older meaning. In mathematical optimisation, optimal does not mean better. It means that no plan exists which beats this one, and that the claim can be handed to a sceptic in a form they can check without redoing any of the work. That is an odd thing to be able to buy. It has a price, and it has a boundary past which it is not for sale at any price.

Pricing a life, 1945

In 1945 George Stigler asked a strange question in print: what does it cost to keep a man alive? Not comfortably; alive, by the standard of the day. The National Research Council had published its 1943 allowances, and for a moderately active man weighing 154 pounds they came to nine numbers a day. Three thousand calories, 70 grams of protein, 0.8 grams of calcium, 12 milligrams of iron, and five vitamins: A, thiamine and riboflavin (B1 and B2), niacin, and ascorbic acid, which is vitamin C.[1] Nine floors, none of them negotiable, and every one of them will matter later.

Stigler had 77 commodities to choose from and the August 1939 retail price of each, averaged by the Bureau of Labor Statistics across 51 American cities. Which combination met all nine minimums for the least money?

What makes that question answerable is the shape of the table behind it. For each of the 77 commodities Stigler recorded a full nutritional breakdown alongside the price: how much of each of the nine you get for one dollar spent on it. Seventy-seven rows, nine columns, 693 numbers, only 123 of them zero.[19] A dollar of wheat flour buys 44,700 calories and 33 milligrams of riboflavin. A dollar of beef liver buys 2,200 calories and 51 milligrams. Whether liver is worth buying is not a question about liver; it is a question about what else is in the basket.

The paper is "The Cost of Subsistence," twelve pages in the Journal of Farm Economics, written by a man who would collect a Nobel for something else entirely thirty-seven years later.[1][13] He could not answer his own question, and he says so, in a sentence that deserves a second reading. It is a working economist describing the absence of a tool that now arrives with one line in a terminal:

Thereafter the procedure is experimental because there does not appear to be any direct method of finding the minimum of a linear function subject to linear conditions.[1]

So he did it by hand. He struck out everything dominated by something cheaper, which removed all meats except liver (stop making that face: the British have built an entire genre out of chicken livers, so evidently anything is possible), all sugars, all beverages and the patented cereals, and searched what was left. His answer was $39.93 a year.

That is 1939 money. The Minneapolis Fed's consumer price index sits at 41.8 for 1939 and 1004.8 for 2026 on the same 1967 base, a factor of about 24.[14] So Stigler's subsistence diet costs roughly $960 a year in today's terms, or $2.63 a day. Hold on to that number for a moment.

Two years later the tool existed. In the autumn of 1947 Jack Laderman, at the National Bureau of Standards, took the full problem, all 77 commodities rather than Stigler's shortlist, and put it through the simplex method, which George Dantzig had invented that summer: a procedure that walks from one candidate plan to a better one and stops when no better neighbour exists. It works on anything you can write as a linear objective under linear conditions, which is what a linear program is. Stigler's diet is one. Dantzig described the operation much later: nine clerks, each handed eight or nine of the 77 columns, working hand-cranked desk calculators, about 120 man-days between them.[2] They got $39.69.

Stigler was wrong by twenty-four cents a year. Six tenths of one per cent.[1][8]

Now convert that too. Twenty-four cents of 1939 is $5.77 today. Nine clerks, four months of collective arithmetic, to close a gap of under six dollars a year.

Written like that it sounds like the most poorly allocated labour in the history of the Bureau of Standards, and it is exactly the point. They were not buying the six dollars. The story is usually told as the machine beating the man, and it is not that either. The man was essentially right: four of his five commodities survive into the optimal basket at nearly the same quantities, and the optimiser mostly swaps his evaporated milk for two and a half pounds of beef liver. What the 120 man-days bought was the knowledge that no better diet existed, plus a short object that demonstrates it. That object is the subject of this piece, and it arrives two sections down.

Run the same 77 columns today, on a laptop, with an open-source solver, and it comes back in a few milliseconds with the same five commodities.[3] Nine orders of magnitude have gone,[18] and none of them came off the answer. They came off the price of being sure of it.

Three parts and no others

Before the object, the anatomy of the thing that produces it, because the guarantee only exists for problems of a certain shape. A model of this kind has three parts and no others: variables you get to choose, one quantity you are pushing up or down, and conditions any choice has to respect. Stephen Boyd and Lieven Vandenberghe, whose textbook is where most engineers meet this material and which the authors give away as a PDF, write it as minimise f₀(x) subject to f_i(x) ≤ b_i, and name the pieces: x is the optimization variable, f₀ the objective function, the f_i the constraint functions.[4] Stigler's variables were dollars per day spent on each commodity, his objective their sum, his constraints the nine nutritional floors.

Shrink it to two variables and the whole thing fits on a page. A feed producer blends soybean meal at fifty cents a pound with corn meal at eighteen. The batch has to reach a hundred pounds, carry at least thirty pounds of protein, stay under seven pounds of fibre, and use no more corn meal than the silo holds.

Every blend meeting all four conditions lies in the shaded region. The region has a name, the feasible set, and what lies outside it is not a worse plan but no plan at all. The dashed line is a price: every blend along it costs the same. Push that line down and to the left until it is about to leave the region, and it comes to rest touching a single corner. Sixty pounds of soybean meal, forty of corn, $37.20.

The corner is not an accident of these numbers. When the objective is linear and the feasible set is a polygon, an optimum always sits at a corner, which is why the simplex method never looks anywhere else. With two variables you can list all five corners and compare them by hand. With seventy-seven you cannot, because the number of corners grows combinatorially with the constraints. That gap is the whole reason there is an algorithm.

What the corner comes with

When the solver returns the diet, it returns nine other numbers with it, one for each of the nine floors from the top of this piece: the amount the daily bill would rise if that minimum went up by one unit. These are the shadow prices, one per condition, and what they price is not a food but a requirement. Multiply each of the nine by its requirement and add them together, and you get the cost of the diet. The sum is exact.

Riboflavin, vitamin B2, turns out to be the most expensive single thing about staying alive at 1939 prices, and calories are not even second.

That is a fact about the table, not a taste of the model's. Buying a nutrient from its single cheapest source puts a ceiling on what it can cost per unit, and comparing that ceiling to the shadow price says how much the rest of the basket helps. Calories come from wheat flour and the diet pays 38 per cent of the ceiling, because calories arrive as a by-product of everything else. Riboflavin comes from beef liver and the diet pays 83 per cent: there is almost nowhere to hide from it.[19] That is why two and a half pounds of liver are in the answer at all, and why riboflavin ends up the widest slice above. Four of the nine minimums cost nothing at the margin: the protein, the iron, the thiamine and the niacin arrive free, as a by-product of buying enough of everything else. And the bar sums to 10.87 cents a day, which is the price of the diet, and the $2.63 you were asked to hold on to earlier.

That identity is the proof. The solver hands back two objects, a diet and a set of prices, and each one certifies the other. The diet shows the prices cannot be higher; the prices show the diet cannot be cheaper. No one has to trust the solver, rerun it, or audit the path it took. Those nine prices, taken together, are what the field calls the dual solution. Boyd and Vandenberghe call it "a certificate that proves x is optimal," and the word is meant literally.[4]

This is what convexity buys, and it is the only thing convexity buys. A set is convex when the straight line between any two of its points stays inside it: no dents, no holes, no separate pieces. A function is convex when it curves like a bowl, with one bottom rather than several. In a convex problem, meaning a convex objective over a convex feasible set, every local minimum is also the global one,[4] which is what licenses an algorithm that only ever improves locally to stop and be believed. R. Tyrrell Rockafellar, whose Convex Analysis is the book the field reaches for when it wants to be rigorous, put the boundary in one sentence:

In fact the great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity.[5]

He wrote it immediately after observing that in convex problems every locally optimal solution is global. The line circulates stripped of that setup, which makes it sound like a matter of taste. It is a claim about which problems can produce a certificate at all.

The other side of the line

Cross it and the certificate goes.

The usual test at a candidate point is the Karush-Kuhn-Tucker conditions, which ask about slopes and nothing about curvature: is there any direction you could step that improves the objective without breaking a constraint? If there is none, the point passes.[15] In a convex problem, passing is enough, and the point is optimal. Outside convexity, passing drops back to necessary but not sufficient. A point can pass the test and be a saddle.

A saddle is a point that is a minimum if you walk in one direction and a maximum if you walk in another. The tangent is flat either way, which is exactly why a test that only looks at first derivatives cannot separate the two panels above. So what comes back from a non-convex solver is a local answer, and if you are fortunate a bound: a proof that nothing beats that answer by more than some stated amount. When the amount refuses to shrink to zero you own an interval rather than a point, and the width of the interval is the part of the guarantee you did not get.

How thin is the line? Take a quadratic objective, the mildest curvature there is, and bend it the wrong way along a single direction. One negative eigenvalue in the matrix of second derivatives is enough: minimising it becomes NP-hard, meaning no known method handles every instance without the work exploding as the problem grows.[6] And there is a result that does more for the intuition. Hand someone a point in such a problem and ask them to decide whether it fails to be a local minimum. That question is NP-complete too.[7] Not finding the answer. Checking someone else's.

Two men, one object, no contact

One more thing before we leave the certificate, and it is a historical one, because the object at the centre of this piece was built twice.

The simplex method has two origin stories and they never met.

In 1938 the laboratory of the Soviet Plywood Trust asked a young Leningrad mathematician how to distribute work across veneer-cutting machines of differing productivity. Leonid Kantorovich tells it himself in his Nobel autobiography: "In 1938, as professor of the university, I acted as a consultant for the Laboratory of the Plywood Trust in a very special extreme problem."[9] The booklet he published the following year is linear programming. It was received badly. Mathematical methods in economics were a Western and therefore anti-Marxist school; a colleague warned him as much in the spring of 1939, and his 1943 paper on value was rejected in 1945 and appeared only years later in abridged form.[10]

In 1946 the United States Air Force Comptroller's office challenged its mathematical adviser to mechanise the planning process. The adviser was Dantzig. He invented the simplex method the following summer, and on 3 October 1947 took the problem to von Neumann, who cut him off after a minute with "Oh that!" and then spent ninety minutes teaching him the duality behind those nine shadow prices, which he had not known existed.[11]

Two men, one object, no contact, and the whole thing arriving at the same committee in 1975. Kantorovich shared that year's Nobel with Tjalling Koopmans for the theory of optimum allocation of resources. Dantzig received the National Medal of Science the same year, and a reviewer in the Bulletin of the AMS later called the omission from the prize "inexplicable, disappointing and outrageous."[12]

This pattern is common enough that sociology named it. Robert Merton called such episodes multiples, and argued that independent simultaneous discovery is the normal case in science rather than the curiosity.[16] The Cold War produced a run of them, and the closest parallel to this one is the 1964 physics Nobel: half to Charles Townes in the United States, a quarter each to Nikolay Basov and Aleksandr Prokhorov in the Soviet Union, for quantum-electronics work done twice over without contact.[17]

One correction while we are here, because the story is everywhere and it is wrong in a specific way. Dantzig did once mistake two famous unsolved problems for a homework assignment and solve them. They were problems in mathematical statistics, in Neyman's class at Berkeley, around 1939, and they have nothing to do with linear programming, which he invented eight years later. He says so plainly in the same memoir that people quote for the anecdote.[11] The story is better without the embellishment anyway: he did not stumble into linear programming, he was hired to build it. Which is still how it happens.

What this is for

A friend forwarded me a job advertisement last week. A Zurich running-shoe company is looking for someone to build optimisation and scenario models across its supply chain, to let planners see the constraints they are actually working under and quantify what a given trade-off costs. Strip the nouns and it is Stigler's question with a larger table: which combination, under which floors and ceilings, for the least money.

It is also Markowitz's question from 1952, with variance in place of cost. And it is, without metaphor, how a biologist predicts whether a bacterium will grow: flux balance analysis is a linear program whose conditions are the cell's own chemistry, every reaction balanced so that nothing piles up inside (the stoichiometric matrix), and the cell is treated as though it were solving it for growth.

The warehouse, the pension fund and the cell run the same machinery. They also share its failure point. The certificate starts coming apart as soon as the decisions stop being divisible, and it keeps coming apart from there. Nobody buys 2.57 lorries or opens a third of a warehouse, and the moment you write that down the feasible set is full of holes and the corner need not be a legal answer at all.

Which raises the questions I would want answered next, roughly in that order. What comes back when the answer has to be a whole number, and what has become of the corner? If the certificate is gone, what does a solver hand you instead, and how would you know whether it is worth anything? And what happens when the numbers you are optimising against were guesses to begin with, which in finance they always are?

Do not worry though. Nothing above becomes false past that line. It stops being provable, which is a different problem, and a more expensive one.

References

1. George J. Stigler, "The Cost of Subsistence," Journal of Farm Economics 27, no. 2 (May 1945): 303–314. The prices are his Table 1, from Bureau of Labor Statistics retail averages for August 1939 across 51 large cities; the quoted sentence is on p. 310; the $39.93 diet is Table 2, p. 311.
2. George B. Dantzig, "The Diet Problem," Interfaces 20, no. 4 (1990): 43–47. The nine clerks, the desk calculators and the 120 man-days come from this recollection, written forty-three years after the fact. No contemporary report from the National Bureau of Standards appears to survive, and the figures should be read as Dantzig's memory rather than as an archival record.
3. stigler.py in the repository linked below. Across the machines this has run on the solve lands between two and nine milliseconds, and the committed transcript out/stigler.txt carries whatever the last run produced rather than a number typed in by hand. The order of magnitude is the claim; the millisecond is not.
4. Stephen Boyd and Lieven Vandenberghe, Convex Optimization (Cambridge: Cambridge University Press, 2004), available in full at web.stanford.edu/~boyd/cvxbook. The anatomy is §1.1, p. 1; local optimality implying global optimality is §4.2.2, pp. 138–139; the certificate language is §5.5.1, pp. 241–242.
5. R. Tyrrell Rockafellar, "Lagrange Multipliers and Optimality," SIAM Review 35, no. 2 (June 1993): 183–238, at p. 185.
6. Panos M. Pardalos and Stephen A. Vavasis, "Quadratic Programming with One Negative Eigenvalue Is NP-Hard," Journal of Global Optimization 1, no. 1 (1991): 15–22.
7. Katta G. Murty and Santosh N. Kabadi, "Some NP-Complete Problems in Quadratic and Nonlinear Programming," Mathematical Programming 39, no. 2 (1987): 117–129.
8. S. Garille and Saul I. Gass, "Stigler's Diet Problem Revisited," Operations Research 49, no. 1 (2001): 1–13. The 1947 optimal basket, including the beef liver, is their Table 3.
9. Leonid Kantorovich, autobiography, in Les Prix Nobel 1975 (Stockholm: Nobel Foundation, 1976). His 1975 Nobel lecture does not mention the Plywood Trust; the story comes from this note and from his own 1939 booklet, translated as "Mathematical Methods of Organizing and Planning Production," Management Science 6, no. 4 (1960): 366–422.
10. Ivan Boldyrev and Till Düppe, "Programming the USSR: Leonid V. Kantorovich in Context," British Journal for the History of Science 53, no. 2 (June 2020): 255–278.
11. George B. Dantzig, "Reminiscences about the Origins of Linear Programming," Technical Report SOL 81-5, Systems Optimization Laboratory, Stanford University, April 1981.
12. Richard W. Cottle, review of The Basic George B. Dantzig, Bulletin (New Series) of the American Mathematical Society 48, no. 1 (2011): 123–129.
13. Stigler received the Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel in 1982, for work on industrial structures, markets and regulation. Nothing to do with diets.
14. Federal Reserve Bank of Minneapolis, "Consumer Price Index, 1800–": annual average index 41.8 for 1939 and 1004.8 for 2026, on a 1967 = 100 base, giving a factor of 24.04. An independent CPI calculator gives 24.03 for the same pair of years, which is close enough that the third digit is not worth arguing about.
15. Named for William Karush, whose 1939 master's thesis contains them, and for Harold Kuhn and Albert Tucker, who published them independently in 1951. Boyd and Vandenberghe treat sufficiency under convexity in §5.5.3.
16. Robert K. Merton, "Singletons and Multiples in Scientific Discovery: A Chapter in the Sociology of Science," Proceedings of the American Philosophical Society 105, no. 5 (1961): 470–486.
17. The Nobel Prize in Physics 1964, awarded "for fundamental work in the field of quantum electronics, which has led to the construction of oscillators and amplifiers based on the maser-laser principle": one half to Charles Hard Townes, one quarter each to Nicolay Gennadiyevich Basov and Aleksandr Mikhailovich Prokhorov.
18. One hundred and twenty man-days at eight hours is 3.5 million seconds of human arithmetic, against something near five thousandths of a second now. That is a ratio around 7 × 10⁴, which rounds to nine orders of magnitude. Ten would mean a factor of ten billion, so ten was too generous.
19. Both figures come from stigler.py, which prints the whole table. The 77 by 9 matrix is 82 per cent dense, which is unusual: real supply-chain models of this shape are almost entirely zeros, and that sparsity is most of why they are tractable at all.

Data and code

Everything computed here is reproducible: github.com/Denis-Joly/what-optimal-means

stigler.py solves the 1947 problem on all 77 commodities and prints both the diet and the nine shadow prices, along with the check that the two objective values agree to machine precision. blend.py is the two-variable feed problem, and enumerates every corner of the polygon by brute force so you can see the corners the simplex method is choosing between. make_figures.py writes all four figures as SVG.

If you have never pulled someone else's code before, the repository's README is written for exactly that, at length: what to install, what each command actually does, what the output looks like when it works, and what to try when it does not. The short version is five lines.

git clone https://github.com/Denis-Joly/what-optimal-means
cd what-optimal-means
python3 -m venv .venv && source .venv/bin/activate
python3 -m pip install -r requirements.txt
make

The third line is not optional politeness. A Homebrew or system Python will refuse to install anything at all and answer error: externally-managed-environment, which is the interpreter your operating system depends on protecting itself. A virtual environment is a private Python belonging to that folder, so the two packages this needs cannot collide with anything else you have. python3 -m pip rather than plain pip for the same reason: it installs into the interpreter that is about to run the code, instead of whichever one happens to be first on your path.

Reading the code in a browser needs nothing at all, not even an account, and the output of every script is committed alongside it. make reruns everything and rewrites every figure in this post from scratch, so a number in a sentence above cannot drift away from the number the code produces.

The commodity table is Stigler's own Table 1: 77 commodities, August 1939 prices, and the amount of each of nine nutrients obtainable for one dollar. It is committed to the repository as a plain CSV, in the transcription distributed with Google OR-Tools, so the numbers being solved are visible rather than buried in a library. The solver is HiGHS, driven through PuLP; both are open source, and the same models would go to a commercial solver by changing one argument.

One honest gap. The rerun returns $39.66 a year against the $39.69 Dantzig reports, on the same five commodities and within a pound or two on every quantity. The difference is rounding in the transcribed nutrient table and the convention of multiplying a daily cost by 365. It is not a different answer, and I would rather print it than round it away.