Priced hospital menu variety at +37% food cost with a MILP

Menu variety had no price, so it lost every budget argument

A hospital food-service manager has to keep ingredient cost down, keep every patient inside a clinical nutrition range, and keep menus varied enough that patients eat. A patient who stops eating is a clinical problem. Manual planning usually gives up one of the three, and the manager has no number for what the trade costs. Variety is the one that gets cut, because it sounds like a preference while cost and nutrition sound like requirements. We set out to answer one question for that manager: what does a varied menu cost per patient, compared with the cheapest menu that is still clinically compliant? Success meant a dollar figure per diet, from menus that pass every nutrient bound.

The model runs on public nutrition data and synthetic prices

• 41 ingredients in five food groups (10 fruit, 6 vegetable, 9 grain, 10 protein, 6 fat), each with 13 nutrients per gram from USDA food data.
• 5 clinical diets: normal male, normal female, diabetic, high cholesterol and DASH (high blood pressure). Daily bounds follow Health Canada guidance, scaled to a 400-patient baseline. Per-meal calorie windows use a 35/40/25 breakfast/lunch/dinner split from Women’s College Hospital estimates, and the diabetic diet adds a 45–60 g carbohydrate window at every meal.
• 17 culinary rules that block pairings such as oatmeal with beef or granola with salmon.
• Prices are synthetic, based on wholesale averages, so the model could be shared without a supplier agreement. Every dollar figure on this page depends on them.

One 3-day block has 9 meals, 261 eligible ingredient-meal pairs and 686 decision variables.

Four modelling choices turned variety into a dollar figure

Yes/no menu rules forced a mixed-integer model

The model makes two kinds of decision at once: whether ingredient i is on the plate at meal j (binary), and how many grams (continuous). A linking constraint ties them together, so an unselected ingredient gets exactly zero grams and a selected one lands in a realistic portion range for that meal. A pure linear program cannot express “exactly one fruit per meal” or “no oatmeal with beef”, so we rejected it. The original proposal planned Excel Solver, which we dropped because the model outgrew its variable limits. We built it in Python on SciPy’s HiGHS MILP solver.

Each of the 11 constraint families closes a loophole the solver found

Without per-meal calorie windows, the solver put almost all calories into one meal. Without a diabetic carb window per meal, it stacked carbs into one spike while meeting the daily total. Without composition rules, breakfast was nutritionally valid and unrecognisable. Without the culinary rules, it served granola with salmon because the pairing was cheap. Each family in the appendix table exists because a run produced something a dietitian would reject.

We made variety a hard rule so the answer comes out in dollars

We could have added a variety penalty to the objective. That would need an exchange rate between dollars and patient satisfaction, and any rate we chose would decide the answer. Hard rules avoid that: we solved every diet three times with identical constraints except the repeat rules, and the cost difference between runs is the price of variety. The three runs are: cost only (repeats allowed), no ingredient twice in one day, and that plus no ingredient on more than 2 of the 3 days.

The one-fruit-per-meal rule carries the highest shadow price in every diet

Integer programs do not produce usable dual values, so we solved the LP relaxation of the strictest model, with every binary relaxed to the range 0 to 1, and read the shadow prices. In all five diets, the nine “exactly one fruit per meal” constraints were the most expensive, at $0.29 to $0.41 each at the margin. No nutrient bound made any diet’s top 10. The relaxed costs ($6.08 to $6.83) sit below the integer menus, as a lower bound should. Among nutrients, the binding pressure shows up in the compliance check below instead: in the diabetic menu, fibre sits on its floor and potassium almost on its ceiling.

Limiting repeats raised food cost 37%, and every menu met its bounds

* stopped at the 180-second time limit with a feasible menu that is not proven optimal.

• Validation. We checked every menu against every daily nutrient bound for all three days, with a 0.5-unit tolerance. No run violated a bound.
• Optimality. 7 of 15 runs were proven optimal; 8 stopped at the time limit. The result holds on the clean runs: high cholesterol (+44%) and DASH (+42%) were proven optimal under all three rules.
• An anomaly we can explain. For the normal male and diabetic diets, the stricter rule came out cheaper than the looser one ($9.81 vs $9.93, $9.30 vs $9.57). A stricter rule cannot lower the true optimum, so the looser runs stopped before finding their best menu. Their true cost of variety may be somewhat lower than shown.
• Where the cost comes from. In both diets where every run was proven optimal, the 2-of-3-days cap added $0. The whole increase came from banning same-day repeats.
• Variety gained. Distinct ingredients per 3-day menu rose from 17 to 24 on average, and same-day repeats fell from 9–13 per menu to zero.

Recommendation: budget for no same-day repeats, then work on fruit cost

A food-service manager should treat “no ingredient twice in one day” as the default and budget about $0.84 per patient-day for it (estimated, synthetic prices). The 2-of-3-days cap can be added on top: in the cleanly solved diets it cost nothing. The cheapest saving is in fruit, which carries the highest shadow price in every diet. Negotiating fruit prices or approving cheaper fruits for the menu would cut cost more than relaxing any nutrient bound. After rollout, the measure to watch is plate waste and intake by diet, because that is what variety is meant to buy.

Limitations and what we’d do next

• 8 of 15 runs are not proven optimal, and we did not record their optimality gaps. Next: rerun with a longer limit and report the gap for each run, starting with the normal male and diabetic 3-day runs that produced the anomaly.
• Prices are synthetic. The 37% and the $123,000 estimate move with real supplier prices. Next: rerun on one hospital’s actual price list.
• Diets are solved one at a time. A real kitchen feeds every diet from one ingredient pool. Next: a joint model with shared purchasing across diets.
• Shadow prices come from a fully relaxed LP, which can pick fractional menus. Next: fix the chosen menu and re-solve the portions to get dual values for the menu actually served.
• The block is 3 days. A production planner needs a full week or a rotating cycle.

Team and credits

MMA 861 team project. I led the team, and led the formulation, the constraint design and the sensitivity analysis. The model, notebook and write-up were built together.

qMin(i,j) · x(i,j)  ≤  q(i,j)  ≤  qMax(i,j) · x(i,j)