Diet Optimization

Optimization
Operations Research
Linear Programming
Find the cheapest combination of foods that satisfies daily nutrient requirements, framed in physical purchase units of sale.

Diet Optimization

Find the cheapest combination of foods that satisfies every minimum daily nutrient allowance, with quantities measured in physical purchase units of sale (pounds, quarts, dozens, and cans).

[!NOTE] Historical benchmark disclaimer: The commodity prices and nutritional allowances in this template come from George Stigler’s landmark 1939 subsistence diet study (Stigler, 1945). The prices reflect 1939 US retail market conditions and the minimum nutritional standards set by the National Research Council (NRC) in 1941. The template serves as a field-authentic operations research benchmark and educational model, not as contemporary nutritional or dietary advice.

Overview

The Diet Optimization template solves George Stigler’s classic 1939 diet problem: given 77 candidate foods across 9 food categories and 9 essential nutritional allowances, find the least-cost combination of foods that meets or exceeds every daily requirement.

In Stigler’s original mathematical formulation, decision variables were abstracted as dollars spent per day on each food, with nutritional yields expressed per dollar spent. While mathematically convenient for hand calculation, real practitioners and consumers plan diets using physical purchase quantities in real units of sale (e.g. 10 lb. bags of flour, 1 lb. cuts of meat, 1 qt. bottles of milk).

This template reframes Stigler’s classic linear program into a field-authentic grocery purchasing model: - Decision variables: The physical quantity of each food purchased per day in its commercial unit of sale. - Costs: 1939 retail price per unit of sale in dollars. - Nutrients: Actual nutrient content per unit of sale. - Objective: Minimize total daily expenditure subject to meeting or exceeding every dietary minimum allowance.

When you open the workbook, Python for Excel solves the linear program instantly using SciPy’s HiGHS solver and publishes the optimal basket, total daily and annual expenditure, food allocations, and nutrient sensitivity marginals directly to the Results sheet.

Before you start

Requirements. Excel with Python for Excel enabled. The template operates strictly within this workbook and requires no external add-ins, network calls, or database feeds.

Historical solve benchmarks. Stigler posed his diet problem before the invention of George Dantzig’s simplex algorithm: - Stigler (1939 heuristic): Using trial and error and heuristic elimination, Stigler estimated an annual diet cost of $39.93/year (composed of wheat flour, evaporated milk, cabbage, spinach, and dried navy beans). - Laderman (1947 simplex solve): Jack Laderman solved the problem with the simplex method by hand at the National Bureau of Standards Mathematical Tables Project using nine clerks operating desk calculators over 120 person-days, achieving $39.69/year. - True LP optimum (modern solvers): Modern linear programming solvers (and this template) identify the true global optimum at $39.6617/year (equivalent to $0.10866/day in 1939 currency), buying exactly five foods: Wheat Flour (Enriched), Beef Liver, Cabbage, Spinach, and Dried Navy Beans.

Workbook tour

Sheet and range Description Role
Results (A5:C13, A16:G26, A29:G38, A41:E52) Main dashboard displaying solution status, total daily and annual cost, two per-solve checks, the optimal purchase plan (foods with non-zero purchase quantities), nutrient coverage with shadow prices, and suggested limit changes when the inputs make the diet infeasible. Output
Requirements (A5:D14) Daily nutritional allowances for 9 essential nutrients based on 1941 NRC standards, with editable daily minimums. Editable input
Foods (A4:N81) Complete catalog of 77 candidate foods across 9 categories (Grains, Dairy, Fats, Meats, Fruits, Vegetables, Canned Goods, Dried Legumes, Sweets) with unit of sale, retail unit price, optional max quantity cap, and 9 nutrient yields per unit. Editable input
Validation (A5:E20, G5:I20) 15 benchmark cross-checks independently re-verifying the solve against Stigler’s published figures, Laderman’s simplex solution, and modern LP optima. Verification

Using the template

1. Inspect the baseline solve

  1. Open the workbook and allow Python for Excel to complete the baseline calculation.
  2. View the Results sheet:
    • Status: optimal
    • Message: Optimal solution found.
    • Daily cost: $0.1087 per day.
    • Annual cost: $39.66 per year (annualized as daily cost \(\times\) 365).
    • Foods in plan: Exactly 5 foods out of 77 candidate items are selected.
    • Binding nutrients: 5 of the 9 nutrient requirements are exactly binding at their required minimums (Calories, Calcium, Vitamin A, Vitamin B2, and Vitamin C).
    • Checks: Largest limit violation and Duality gap both show PASS in the Status column of the summary (Results!C12:C13).
    • Suggested limit changes: No changes needed - every limit can be met, with a total change of 0.0.

2. Adjust nutrient requirements

  1. Navigate to the Requirements sheet.
  2. Locate the Daily minimum column (Requirements!C6:C14).
  3. Increase the Calories (1000 kcal) requirement from 3.0 to 3.1.
  4. Return to Results: notice the daily cost increases to $0.1095 and the annual cost rises to $39.98/year, reflecting the Calories shadow price ($0.008765 per 1,000 kcal).

3. Exclude or cap a food staple

  1. Navigate to the Foods sheet.
  2. Locate Liver (Beef) in row 34 (Foods!A34:N34).
  3. In the Max daily quantity column (Foods!E34), enter 0 to simulate a consumer who refuses to eat beef liver.
  4. Return to Results: Liver drops out of the optimal plan, and Evaporated Milk (can) enters the diet basket at $0.0086/day to satisfy Vitamin A and Riboflavin needs, raising total annual cost to $39.80/year.

4. Make the diet infeasible and read the suggested repair

  1. On the Foods sheet, enter 0 in the Max daily quantity column (Foods!E) for the 30 foods that supply Vitamin C: rows 18, 19, 24, 34, 42, 45 to 52, 53 to 62, and 64 to 70.
  2. Return to Results: the status is infeasible, and the plan and coverage tables are empty. No food can supply the 75 mg Vitamin C minimum.
  3. Read Suggested limit changes (Results!A41:E52): Vitamin C (mg) is listed with a type of Minimum (at least), a current minimum of 75.0, a suggested minimum of 0.0, and a change of -75.0. The total row shows 75.0, the Vitamin C shortfall.

Inputs and settings

Requirements table (Requirements!A5:D14)

  • Nutrient (col A): Name of the essential nutritional factor.
  • Unit (col B): Physical unit of measurement (1000 kcal, grams, milligrams, or KIU). Energy is expressed in 1,000 kcal units (3.0 represents 3,000 kcal).
  • Daily minimum (col C, blue input): Minimum required daily allowance for an average sedentary adult male. Values must be non-negative numbers.
  • Notes (col D): Historical 1941 National Research Council (NRC) recommended dietary allowance context.

Foods table (Foods!A4:N81)

  • Category (col A): Natural food category (Grains & Cereals, Dairy & Eggs, Fats & Oils, Meat, Poultry & Fish, Fresh Fruits, Fresh Vegetables, Canned Goods, Dried Fruits & Legumes, Sweets & Miscellaneous).
  • Food (col B): Specific food commodity name.
  • Unit of sale (col C): Commercial retail purchasing unit (e.g. 10 lb., 1 lb., 1 qt., 1 doz., No. 2 can).
  • Cost per unit ($) (col D, blue input): 1939 retail price per unit of sale in US dollars.
  • Max daily quantity (col E, blue input): Optional upper purchase limit per day. Leave blank for unbounded purchase. Set to 0 to exclude the food.
  • Nutrient yield columns (cols F to N): Actual content of Calories, Protein, Calcium, Iron, Vitamin A, Vitamin B1, Vitamin B2, Niacin, and Vitamin C provided by one full unit of sale.

How results are calculated

  1. Unit conversion: Each food’s nutrient yield per unit of sale \(A_{j,i}\) and unit price \(c_i\) form the matrix of linear coefficients: \[\text{intake}_j = \sum_{i=1}^{77} A_{j,i} \cdot x_i\] where \(x_i \ge 0\) is the quantity of food \(i\) purchased per day in its commercial unit of sale.

  2. Linear programming formulation: \[\begin{aligned} \text{minimize} \quad & \sum_{i=1}^{77} c_i \cdot x_i \\ \text{subject to} \quad & \sum_{i=1}^{77} A_{j,i} \cdot x_i \ge \text{minimum}_j \quad \text{for each nutrient } j \\ & 0 \le x_i \le \text{max\_quantity}_i \quad \text{for foods with upper limits} \end{aligned}\]

  3. Solver execution: The problem is solved using SciPy’s HiGHS simplex and interior-point solver (scipy.optimize.linprog(method="highs")).

  4. Independent verification: The solution vector \(x^*\) is verified against primal feasibility tolerances (\(< 10^{-6}\)) and dual optimality conditions before publication.

Reading the results

  • Summary checks (Results!A12:C13): Two checks on your own sheet data, computed on each solve. The Status column shows PASS or FAIL, or is blank when the solve does not return an optimal plan.
    • Largest limit violation: The largest violation of any nutrient minimum, food cap, or nonnegativity bound, from check_solution. It passes when the solution is feasible within tolerance.
    • Duality gap: The gap between the primal and dual objective values of the linear program, from duality_gap. It passes when the gap is at most 0.00001. The diet is a linear program, so no MIP gap is shown.
  • Optimal purchase plan (Results!A16:G26): Lists only the foods selected with positive purchase quantities. In the baseline Stigler solution, exactly five staples are bought:
    • Wheat Flour (Enriched): 0.082 units/day (0.82 lb./day), costing $0.0295/day ($10.77/year). Primary source of calories, iron, and thiamine.
    • Liver (Beef): 0.0071 units/day (0.11 oz./day), costing $0.0019/day ($0.69/year). Potent low-cost source of Vitamin A, riboflavin, and niacin.
    • Cabbage: 0.303 units/day (0.30 lb./day), costing $0.0112/day ($4.09/year). Primary source of Vitamin C.
    • Spinach: 0.062 units/day (0.06 lb./day), costing $0.0050/day ($1.83/year). Secondary source of Vitamin A, Vitamin C, and iron.
    • Navy Beans, Dried: 1.034 units/day (1.03 lb./day), costing $0.0610/day ($22.28/year). Major source of protein, calories, and calcium.
  • Nutrient coverage and sensitivity (Results!A29:G38):
    • Coverage %: Actual intake divided by daily requirement minimum. Values above 100% indicate nutrient surplus (e.g. Iron is covered at 504%, Protein at 211%).
    • Status: Indicates whether the nutrient is exactly at minimum or has a surplus.
    • Shadow price ($/unit): The marginal increase in total daily diet cost if the nutrient requirement is raised by one unit. Non-binding nutrients have a shadow price of $0.00. Calories have a shadow price of $0.008765 per 1,000 kcal; Calcium has a shadow price of $0.031738 per gram.
  • Suggested limit changes (Results!A41:E52): Filled only when the model is infeasible. Each row names a limit (the nutrient minimum), its type (Minimum (at least)), the current minimum, the suggested minimum, and the change. The total row sums the absolute changes of the rows shown (up to 10 rows). The suggestion is one way to make the diet feasible; other repairs may exist. When the baseline is feasible, the block shows No changes needed - every limit can be met with a total of 0.0. If no repair can be computed, it shows No repair could be computed - see the message above and the total is blank.

Saving, sharing and App mode

  • Saving: Save the workbook normally (.xlsx). Python recalculates on file open and whenever inputs change.
  • Sharing: Workbooks can be shared with any Excel user. When opened in Excel Online or desktop Excel with Python for Excel, calculations refresh reactively.
  • App mode: In App mode, users interact with the workbook purely through Excel worksheet cells without exposing raw Python code.

Errors, empty states and limits

Solver statuses

  • optimal: Proven global least-cost diet found.
  • infeasible: No combination of candidate foods can satisfy all nutritional requirements simultaneously (for example, if candidate foods rich in a required nutrient are excluded or capped too strictly). Results tables are cleared and the summary reports "No combination satisfies all the limits.". The Suggested limit changes block lists the nutrient minimums to lower; see Reading the results.
  • error: The input table contains non-numeric entries, negative prices, or negative nutrient yields. A danger callout appears in the task pane naming the invalid cell or column.

Empty state

  • If the Foods table is cleared, the notebook falls back to the built-in Stigler 1939 dataset to maintain workbook integrity.

Limitations and when to use this

Historical and pedagogical context

This template models the classic 1939 Stigler subsistence problem, which is a foundational benchmark in the history of linear programming and operations research. It is designed for operations research teaching, linear programming demonstrations, and historical benchmarking.

Realism caveats

  1. Fractional package quantities: The linear program assumes continuous divisible quantities (e.g. buying 0.082 ten-pound bags of flour per day). In reality, grocery purchases come in discrete packages.
  2. Extreme staple concentration: Stigler’s minimum-only model concentrates 83% of total spending into wheat flour and dried beans, with cabbage and spinach providing vitamins. It contains no palatability, variety, or cultural food preferences.
  3. No nutritional upper bounds: The classical model sets only lower bounds. Real human diets require upper bounds on sodium, saturated fat, cholesterol, and total calories to prevent chronic disease.
  4. Missing constraints in modern diet planning: Real-world diet formulation tools (such as the USDA Thrifty Food Plan, WHO Optifood, and FAO least-cost models) add:
    • Upper limits on micronutrients and macronutrient energy shares.
    • Food-group serving constraints (minimum servings of dairy, fruits, vegetables, and proteins).
    • Palatability and variety constraints (capping any single staple at a reasonable daily serving size).

Free alternatives

Excel Solver, built into desktop Excel (it is not available in Excel for the web), and the free OpenSolver add-in for Windows Excel (a COIN-OR CBC add-in with no stable release since 2020) can both solve this same diet model. Excel Solver’s Simplex LP engine accepts up to 200 decision variables and 100 constraints, which covers the sample’s 77 foods and 9 nutritional allowances. This workbook solves the model as a linear program with HiGHS through SciPy’s scipy.optimize.linprog, running in the browser. What it adds is the field layout on the Foods and Requirements sheets, live recalculation when inputs change, nutrient shadow prices with the meaning stated on Results, independent constraint checks, and a Validation sheet that checks the solve against Stigler’s 1939 problem and Laderman’s 1947 simplex solution. When the sheet inputs make the diet infeasible, the Results sheet also names which nutrient minimums to lower, with the current value, the suggested value, and the change.

Customizing as an author

To adapt this model for modern dietary analysis or specialized animal feed / ration optimization: - Updating food items and prices: Add or replace rows in the Foods sheet with modern retail foods, grocery prices, and USDA FoodData Central nutritional profiles. - Adding upper bounds and variety constraints: A practitioner can extend the linear program formulation in notebook.py by adding nutrient upper bounds (e.g. sodium or saturated fat limits), food-group serving caps, or variety constraints, which are not included in this classical subsistence model. - Capping individual foods: Use the Max daily quantity column on the Foods sheet to enforce realistic daily intake limits (e.g. capping navy beans at 0.5 lb./day).

Tool commands

  • Regenerate workbook: uv run python .agents/skills/python-template/scripts/generate-workbooks.py templates/optimization/diet-optimization
  • Run offline scenarios: uv run python .agents/skills/python-template/scripts/run-scenarios-offline.py templates/optimization/diet-optimization
  • Run acceptance gate: uv run python .agents/skills/python-template/scripts/template-gate.py diet-optimization --generate

Developer reference

Notebook implementation

notebook.py is authored as a reactive Marimo application conforming to the Boardflare Python-for-Excel specification: - # engine-modules: table: Engine synchronization copies engine/core.py and engine/table.py into the notebook. - bf.inputs(...): Reads named worksheet ranges from Requirements!A5:D14, Foods!A4:N81, and Validation!A5:E20. - Direct solver call: Calls core.solve directly with retail unit prices \(c\), constraint coefficient matrix \(A_{ub}\), right-hand side requirements \(b_{ub}\), and per-food bounds. - check_solution(...): Validates feasibility, constraint compliance, and variable bounds independently before output generation. Its largest violation is published as Largest limit violation. - duality_gap(...): Computes the LP duality gap of an optimal solution, published as Duality gap. The notebook passes the same constraint and bound arrays as the solve. - explain_infeasible(...): Runs only when the status is infeasible. It relaxes the nutrient minimum rows in an elastic model and returns the suggested limit changes published to Suggested limit changes. Variable bounds are not relaxed. - bf.publish(...): Publishes structured DataFrames to summary, plan, coverage, repair, and validation spill anchors.

# Core solve call in notebook.py
solution = solve(
    c=food_costs,
    A_ub=A_ub,
    b_ub=b_ub,
    bounds=bounds,
    sense="min",
    time_limit=DEFAULT_TIME_LIMIT,
)

How the calculation works

  1. Input parsing & coercions: Numeric values in prices and nutrient columns are sanitized with as_number, stripping currency symbols and thousands commas.
  2. Constraint formulation:
    • Minimum nutritional requirements: \(-\sum_{i} A_{j,i} x_i \le -\text{minimum}_j\)
    • Food availability bounds: \(0 \le x_i \le \text{max\_quantity}_i\)
  3. HiGHS dual extraction: Shadow prices are extracted from solution.shadow_prices["ineq"] for all binding constraint rows.

Validation and expected results

The Validation sheet contains 15 benchmark cross-checks evaluated against published historical literature: 1. George Stigler (1939): Heuristic guess $39.93/year. 2. Jack Laderman (1947): Hand simplex solve $39.69/year. 3. True LP Optimum: Modern solver annual cost $39.6617/year (daily cost $0.108662/day). 4. Food basket allocations: Exact annual expenditures for Wheat Flour ($10.77), Beef Liver ($0.69), Cabbage ($4.09), Spinach ($1.83), and Navy Beans ($22.28). 5. Binding nutrient allowances: Exact binding intakes for Calories (3.00), Calcium (0.80), Vitamin A (5.00), Vitamin B2 (2.70), and Vitamin C (75.00).

All 15 cross-checks report PASS.

Changelog

2026-10-28

  • Implemented build-time dataset packs under datasets/ (stigler.py and food_blending.py), supporting variant generation via build_workbook(output_path, dataset=...) (strategy item D2).
  • Folded food-blending (limSolve pet-food blending benchmark, cost 700/22 ≈ $31.8182/kg) into diet-optimization as a build-time dataset variant with dedicated equivalence tests.
  • Added infeasibility repair: when the sheet inputs make the diet infeasible, Results names the nutrient minimums to lower (current value, suggested value, change) in a new Suggested limit changes block (Results!A41:E52), computed with explain_infeasible.
  • Added two per-solve checks to the Results summary: Largest limit violation (from check_solution, now including variable bounds) and Duality gap (LP, PASS at or below 0.00001). The summary has a Status column.
  • Moved the optimal purchase plan to Results!A16:G26 and nutrient coverage to Results!A29:G38 to make room for the new rows.
  • Added the vitc-zero scenario: capping all 30 Vitamin C suppliers at zero makes the diet infeasible, and the repair total equals the 75 mg shortfall.

2026-10-25

  • Hand-crafted rebuild replacing generic skeleton-generated layout with field-authentic purchasing model (issue #240).
  • Reframed decision variables from abstract dollars-per-day to physical purchase quantities in commercial units of sale (pounds, quarts, dozens, cans).
  • Structured 77 candidate foods into 9 natural food categories (Grains, Dairy, Fats, Meats, Fruits, Vegetables, Canned Goods, Dried Legumes, Sweets).
  • Created dedicated Requirements sheet with editable daily nutritional minimums.
  • Filtered Results purchase plan to display only selected non-zero foods with unit prices, daily quantities, daily cost, and annual cost.
  • Added comprehensive Validation sheet with 15 published historical cross-checks (Stigler 1939, Laderman 1947, HiGHS LP optimum) all reporting PASS.
  • Accepted advisory pane-clip warning: Foods!A4:N81 (the 77-food table, 9 nutrient columns plus Food/Category/Unit/Cost/Quantity/Cost-per-day) ends at 1515px, past the 1250px task-pane threshold. Narrowing any nutrient or identifying column would clip required per-food data the solver and the user both need; the table is scrollable in Excel, and the gate’s live/static renders show no clipped text.