Stigler's diet problem¶

The cheapest way to eat for a year and stay alive. 77 foods, 9 nutrients, 1939 prices.

✔ Verified against linopy 0.9.0 — objective 0.10866227820675685 dollars/day, matched to rtol=1e-09. Corroborated by Laderman (1947), who published $39.69/year for this data.

This is where linear programming started earning its keep. Stigler posed it in 1945 and got $39.93 by trial and error, admitting there was "no direct method" to do better. In 1947 Jack Laderman at the National Bureau of Standards took it as the first serious test of Dantzig's new simplex method: nine clerks on desk calculators, roughly 120 man-days, for $39.69.

It is in the corpus because every other verified model is a flow of something through a network. This one has no network at all — it is a covering LP, min 1ᵀx subject to Ax ≥ b, which is a different shape of problem reaching the same engine.

The model¶

The same model, as math

Stigler's diet problem (1945): the cheapest set of foods meeting a year's nutritional minimums. Stigler's table is normalised per dollar spent, so a variable is money on a food per day rather than a quantity, and the objective is simply the total. The table is sparse on purpose — a food supplying none of a nutrient has no row, which is how this language spells absence everywhere, and 570 of the 693 cells are non-zero.

Sets¶

Symbol	Meaning
$\mathcal{F}$	index $f$ --- `food` --- the 77 foods Stigler priced, at 1939 prices
$\mathcal{N}$	index $n$ --- `nutrient` --- the nine nutrients a year's diet has to supply

Parameters¶

Symbol	Meaning
$\mathit{nutrient}^{\mathrm{per,dollar}}$	`nutrient_per_dollar` over $\mathcal{F} \times \mathcal{N}$ --- how much of each nutrient a dollar of each food buys
$\mathit{daily\_minimum}$	`daily_minimum` over $\mathcal{N}$ --- how much of a nutrient a day has to supply

Variables¶

Symbol	Meaning
$\mathit{spend}$	`spend` over $\mathcal{F}$ --- dollars per day spent on this food

Objective¶

\[\min \sum_{f \in \mathcal{F}} \mathit{spend}_{f}\]

Subject to¶

meet_requirement

\[\sum_{f \in \mathcal{F}} \mathit{spend}_{f} \cdot \mathit{nutrient}^{\mathrm{per,dollar}}_{f,n} \ge \mathit{daily\_minimum}_{n} \qquad \forall\thinspace n \in \mathcal{N}\]

Variable domains¶

spend

\[\mathit{spend}_{f} \ge 0 \qquad \forall\thinspace f \in \mathcal{F}\]

The tabs start from the instance’s tables — one frame per parameter.

lpspeclinopy

description: >-
  Stigler's diet problem (1945): the cheapest set of foods meeting a year's
  nutritional minimums. Stigler's table is normalised per dollar spent, so a
  variable is money on a food per day rather than a quantity, and the objective
  is simply the total. The table is sparse on purpose — a food supplying none
  of a nutrient has no row, which is how this language spells absence
  everywhere, and 570 of the 693 cells are non-zero.

dimensions:
  food:
    description: the 77 foods Stigler priced, at 1939 prices
    dtype: str
  nutrient:
    description: the nine nutrients a year's diet has to supply
    dtype: str

parameters:
  nutrient_per_dollar:
    description: how much of each nutrient a dollar of each food buys
    dims: [food, nutrient]
  daily_minimum:
    description: how much of a nutrient a day has to supply
    dims: [nutrient]

variables:
  spend:
    description: dollars per day spent on this food
    foreach: [food]
    bounds:
      lower: 0

constraints:
  meet_requirement:
    description: what the basket buys of a nutrient covers the daily minimum
    foreach: [nutrient]
    expression: sum(spend * nutrient_per_dollar, over=food) >= daily_minimum

objective:
  sense: minimize
  description: dollars a day, which is what the variables already are
  expression: spend

# sources: parameter name -> frame or parquet path
with lps.solve('examples/ports/stigler_diet.yaml', sources) as solution:
    solution.objective  # 0.10866227820675685
    solution.dual('meet_requirement')

The model-building half of examples/ports/references/linopy/stigler_diet.py:

def build(tables: dict[str, pd.DataFrame]) -> linopy.Model:
    """The port's tables as a linopy model, column for column.

    ``tables`` is the same mapping the lpspec call binds as ``sources``.
    ``per_dollar`` is the sparse table filled back out: a missing
    (food, nutrient) pair means that food supplies none of that nutrient.
    """
    foods = pd.Index(tables['food']['food'], name='food')
    minimum: pd.Series = tables['daily_minimum'].set_index('nutrient')['value']
    per_dollar: pd.DataFrame = (
        tables['nutrient_per_dollar']
        .pivot(index='food', columns='nutrient', values='value')
        .reindex(index=foods, columns=minimum.index)
        .fillna(0.0)
    )

    m = linopy.Model()
    spend = m.add_variables(lower=0, coords=[foods], name='spend')
    m.add_constraints((spend * per_dollar).sum('food') >= minimum, name='meet_requirement')
    m.add_objective(spend.sum())
    return m

Stigler's table is normalised per dollar spent, so a variable is money on a food per day rather than a quantity, and the objective is just the total. That is his framing, not a convenience: it is what makes the matrix price-independent.

The nutrient table is sparse and stays that way. 570 of the 693 (food, nutrient) cells are non-zero; a food supplying none of a nutrient simply has no row. Row absence is how this language spells "not present" everywhere else, and here it means exactly what a reader would assume.

What it finds¶

food	$/year
navy beans (dried)	22.28
wheat flour (enriched)	10.77
cabbage	4.09
spinach	1.83
beef liver	0.69
total	39.66

Those are the five foods in the historical solution. The 0.08% gap against Laderman's $39.69 is his rounding — nine people with desk calculators — not a different model. Matching the composition is the stronger corroboration; two routes to the same five foods out of seventy-seven is not a coincidence.

What a nutrient costs¶

The duals are the most legible in the corpus — each is what one more unit of that nutrient per day would cost:

nutrient	shadow price
calcium	0.0317
vitamin B2	0.0164
calories	0.0088
vitamin A	0.0004
vitamin C	0.00014
protein · iron · vitamin B1 · niacin	0

Four of the nine requirements cost nothing at the margin: they arrive free alongside the ones that bind. That is the diet problem's actual lesson, and it is a dual, not a primal — which is why the corpus checks duals as well as objectives.

What it exercises¶

A two-dimensional parameter multiplying a one-dimensional variable, reduced along the shared dimension — the same shape KVL needs for its cycle incidence, doing a completely different job. Plus a bare variable as the whole objective, which is as small as an objective gets.

Symbol	Meaning
\(\mathcal{F}\)	index \(f\) --- `food` --- the 77 foods Stigler priced, at 1939 prices
\(\mathcal{N}\)	index \(n\) --- `nutrient` --- the nine nutrients a year's diet has to supply

Symbol	Meaning
\(\mathit{nutrient}^{\mathrm{per,dollar}}\)	`nutrient_per_dollar` over \(\mathcal{F} \times \mathcal{N}\) --- how much of each nutrient a dollar of each food buys
\(\mathit{daily\_minimum}\)	`daily_minimum` over \(\mathcal{N}\) --- how much of a nutrient a day has to supply