Meal planning as a constrained optimisation problem

§ 01Seven picks are not a week

Recipe recommenders pick a dish per slot: score every recipe against a profile, take the best one, move to the next slot. That works for a single dinner and fails for a week, because the things a person cares about over a week are not properties of a dish. Daily energy is a sum over two or three slots. Weekly protein is a sum over fourteen. The chicken bought on Monday comes in a 1 kg tray whether Tuesday uses it or not, and the leftover half of a stew is either Wednesday's lunch or the bin. Each of those couples slots to one another, and a per-slot pick cannot see the coupling.

The Menucesta product page says it in one line: the week is the product, not an isolated recipe. Behind that line there is a model, and it is a fairly ordinary integer programme: binary variables for which recipe goes in which slot, integer variables for how many packages of each product to buy, hard constraints for what must hold and a weighted objective for what I would like to hold. This note gives the formulation, the solver I use, the tricks that keep it solvable at interactive latency, and how I turn the solver's answer into something a person will accept. Where the nutrition numbers come from, and why a language model must not produce them, is N.14.

§ 02Variables, and the data they stand on

The decision variables are few. x[r,d,s] is 1 when recipe r is served on day d in slot s. cook[r,d] is 1 when the recipe is actually cooked that day rather than reheated from a batch. y[p] is the number of packages of product p in the basket, and w[p] the grams of it bought and not used. Everything else, energy, protein, minutes, cost, waste, is a linear expression over those.

Exclusions are not constraints. A recipe with a listed allergen never becomes a variable: it is filtered out when the candidate pool is built, deterministically and before any model, whether an optimiser or a language model, sees it. That is the boundary the product page describes: the IA Chef generates and words the plan; nutrition rules, allergies and the shopping calculation stay outside the model and are checked deterministically. The pool query is boring, and that is its virtue.

-- candidate pool for one profile: the recipes that may become variables
SELECT r.id, r.kcal, r.protein_g, r.minutes, r.batch_days, r.protein_source
FROM recipe r
WHERE r.published
  AND NOT EXISTS (                       -- a hard exclusion, never a penalty
        SELECT 1 FROM recipe_allergen ra
        WHERE ra.recipe_id = r.id AND ra.allergen = ANY(:allergens))
  AND r.kcal BETWEEN :kcal_slot_min AND :kcal_slot_max
  AND r.minutes <= :max_minutes_any_day
  AND (r.season IS NULL OR r.season @> ARRAY[:month])
ORDER BY r.profile_score DESC            -- a rough fit, only to cap the pool
LIMIT 90;

§ 03Hard constraints, and the model in code

Hard constraints are the ones the person would not forgive: one dish per slot; a recipe served at most twice in the week and never twice on the same day; daily energy inside the band; daily protein above the floor; total minutes on a day within that day's budget, where a reheated batch costs a flat five minutes instead of its cooking time; and package coverage, meaning the grams of each product the week uses cannot exceed the grams the basket contains. The last one is what makes the basket a variable of the plan rather than an afterthought.

In OR-Tools CP-SAT the whole thing fits in forty lines. Units are integers throughout: kilocalories, grams, minutes, and money in thousandths of a cent so that a price per gram survives as an integer coefficient. Weights are already multiplied into that common scale.

from ortools.sat.python import cp_model
m = cp_model.CpModel()
x    = {(r, d, s): m.NewBoolVar(f"x{r}_{d}{s}") for r in RC for d in DAYS for s in SLOTS}
srv  = {(r, d): m.NewBoolVar(f"srv{r}_{d}") for r in RC for d in DAYS}
cook = {(r, d): m.NewBoolVar(f"cook{r}_{d}") for r in RC for d in DAYS}
y = {p: m.NewIntVar(0, 12, f"y{p}") for p in PR}                 # packages bought
w = {p: m.NewIntVar(0, 12 * SIZE[p], f"w{p}") for p in PR}       # grams left over
for d in DAYS:
    for s in SLOTS:
        m.AddExactlyOne(x[r, d, s] for r in RC)
    for r in RC:
        m.Add(sum(x[r, d, s] for s in SLOTS) == srv[r, d])       # at most once a day
        fridge = [srv[r, e] for e in DAYS if 0 < d - e <= BATCH[r]]
        m.Add(cook[r, d] >= srv[r, d] - sum(fridge))            # cook unless a batch is in the fridge
        m.Add(cook[r, d] <= srv[r, d])
    m.AddLinearConstraint(sum(KCAL[r] * srv[r, d] for r in RC), KMIN[d], KMAX[d])
    m.Add(sum(PROT[r] * srv[r, d] for r in RC) >= PMIN[d])
    m.Add(sum(MIN[r] * cook[r, d] + REHEAT * (srv[r, d] - cook[r, d]) for r in RC) <= TIME[d])
for r in RC:
    m.Add(sum(srv[r, d] for d in DAYS) <= MAX_REPEAT)
for p in PR:                                                     # the basket is a variable of the plan
    used = sum(G[r][p] * srv[r, d] for r in RC for d in DAYS if p in G[r])
    m.Add(SIZE[p] * y[p] - used == w[p])
same = []                                                        # variety: one protein source, both slots
for d in DAYS:
    for src in SOURCES:
        v = m.NewBoolVar(f"same{d}{src}")
        m.Add(sum(srv[r, d] for r in RC if SRC[r] == src) <= 1 + v)
        same.append(v)
cost  = sum(PRICE_MC[p] * y[p] for p in PR)                      # milli-cents per package
waste = sum(UNIT_MC[p] * w[p] for p in PR)                       # milli-cents per gram, rounded once
mins  = sum(MIN[r] * cook[r, d] + REHEAT * (srv[r, d] - cook[r, d]) for r in RC for d in DAYS)
m.Minimize(W_COST * cost + W_WASTE * waste + W_VAR * sum(same) + W_TIME * mins)
sol = cp_model.CpSolver()
sol.parameters.max_time_in_seconds = 2.0
sol.parameters.num_workers = 8
status = sol.Solve(m)
gap = (sol.ObjectiveValue() - sol.BestObjectiveBound()) / max(1, sol.ObjectiveValue())

The batch link is the only line that needs a comment. cook[r,d] must be 1 whenever r is served on day d and was not served on any of the previous BATCH[r] days; for a recipe that cannot be batched the window is empty, so cook simply equals srv. It is an implication, and that is why I prefer CP-SAT to an LP-flavoured tool here: I write the implication and the solver owns the linearisation.

§ 04Soft objectives, weights, a worked instance

Everything else is a preference, and preferences go into the objective, because a preference written as a constraint is the shortest route to an infeasible model. Four terms: basket cost; the value of the waste, that is grams bought and not used, priced at that product's price per gram; variety events, one for each day whose two slots share a protein source; and cooking minutes. Weights are stated per unit and belong to the profile. In the instance below they are 100 per cost unit, 100 per unit of waste value, 60 per variety event and 2 per minute. Cost and waste on the same weight says I do not care whether money leaves as a purchase or as a bin bag, which is what most people mean by "cheap".

The instance: three days, lunch and dinner, a pool of eight recipes, twelve products with package sizes, prices in illustrative units that belong to no retailer, an energy band of 1,000–1,300 kcal for the two meals together, a protein floor of 70 g per day, time budgets of 45, 45 and 75 minutes, a five-minute reheat, and at most two servings of any recipe. It is small enough to enumerate: 175,616 assignments, 1,040 feasible. The first row picks each day's pair independently by pro-rata ingredient cost, price per gram times grams, the way a recipe app "costs" a dish, with a no-repeat rule for variety, then buys the packages those picks need. The second row is the joint optimum. The third is the joint optimum with repeats forbidden.

Two things in that table are the note. Pro-rata cost differs by 13 % between the first two rows; package cost differs by 89 % and the waste value triples. The pro-rata number is the one a per-slot recommender optimises and it is not the number the person pays. And the third row is the honest one: with repeats forbidden, the joint solver lands on exactly the greedy basket, because in a pool of eight the only coupling worth money was reuse. A solver is only as good as the room the pool gives it, which is why the pool is ninety candidates and not eight, and why "no repeats" is offered to the person with its price attached rather than assumed.

§ 05Choosing a solver and keeping it solvable

Three options and the reasons. Integer linear programming (HiGHS, CBC) is the natural fit when every term is linear and the model is small; the batch implication and the at-most-k logic linearise, but the model gets ugly and the person reading it later pays for that. Heuristics, a greedy construction followed by local search with swaps, are what I reach for when latency must stay under 100 ms and a good answer beats the best one; they cannot tell you how far from optimal you are. CP-SAT gives me the logic natively, an incumbent at any time limit and a bound, so I can report the gap. For a weekly plan solved on request, CP-SAT with a two-second limit and eight workers is the trade I make; a swap-based repair on the same model is the fallback for the interactive path, where a person changes one dish and wants the week fixed now.

Solvable in practice means five habits. Keep the pool at 60–120 recipes, filtered by the query above and never the whole catalogue. Keep the hard constraints to the list in § 03. Break the symmetry between interchangeable days: distinct time budgets per day, which the profile has anyway, do most of it, and fixing the first slot to the lowest-indexed member of any tied set does the rest. Scale every objective term into one integer unit and check the largest coefficient stays well under 2⁵³. And when the model is infeasible, do not return "no plan": a relaxation ladder widens the energy band by 5 %, then drops the variety term, then lifts the repeat cap to three, re-solving at each step, and the plan carries the name of the step that made it feasible. That name is shown to the person, not logged and hidden.

§ 06Explaining the answer to a person

A solver returns assignments; a person asks why. The explanation I produce comes from the same model, not from a language model guessing at the solver's reasons. For each slot: the recipe; its contribution to each objective term, its share of the packages it triggered, its waste share, its minutes, any variety event it caused; whether a daily constraint is tight on that day, energy at the band edge or time at budget; and the best alternatives for the slot, meaning the recipes that, fixed into that slot with the rest of the week re-solved, raise the objective least, with the delta in every term. The last one is the useful one. In the instance above, Tuesday dinner is the chicken and spinach bowl reheated from Monday, Tuesday's time budget is exactly spent, and the day's variety event is that both meals are chicken. The record says what removing that event would cost.

{
  "slot": {"day": "tue", "meal": "dinner"},
  "recipe": {"id": 1291, "name": "chicken and spinach rice bowl",
             "cooked": false, "batch_from": "mon-lunch"},
  "terms": {"cost_share": 0.0, "waste_share": 0.0, "minutes": 5, "variety_events": 1},
  "tight": {"kcal_band": false, "protein_floor": false, "time_budget": true},
  "alternatives": [
    {"recipe": "chicken adobo with rice", "note": "swap with lunch",
     "delta": {"cost": 0.0, "waste": 0.0, "minutes": 0, "variety_events": 0, "objective": 0}},
    {"recipe": "tuna pasta", "new_packages": [{"product": "pasta 500 g", "n": 1}],
     "delta": {"cost": 1.0, "waste": 1.0, "minutes": 15, "variety_events": -1, "objective": 169.7}},
    {"recipe": "salmon with potatoes", "new_packages": [{"product": "salmon 500 g", "n": 1},
                                                      {"product": "potatoes 2 kg", "n": 1}],
     "delta": {"cost": 10.1, "waste": 7.2, "minutes": 50, "variety_events": -1, "objective": 1770.6}}
  ],
  "relaxation_step": null,
  "solver": {"status": "OPTIMAL", "gap": 0.0, "wall_ms": 412}
}

The language model, where it appears, writes the plan's prose from this record and from nothing else: it turns the record into "I repeated the chicken bowl because it was already cooked and Tuesday has forty-five minutes; tuna pasta would avoid two chicken meals for one more package and fifteen minutes." It does not choose, does not add a dish and does not compute a calorie. The general form of that contract, the source stays authoritative and the model narrates, is N.11.

§ 07Failure modes

The solver games the waste term. With a high waste weight it picks small recipes that use exactly a package's worth and starves the person inside the letter of the energy band. The objective was right and the band was wrong: a floor per slot, not only per day, and a minimum serving weight fix it. Every new term earns a look at what the solver will do to satisfy it that I did not intend.

Package brittleness. A catalogue change, a 1 kg tray becoming 750 g, flips a whole week, because coverage is a hard constraint on integer packages. The plan is solved against the catalogue snapshot the basket will be bought from and re-checked against the live one before it is shown; when the basket is compared across supermarkets, as the product does, it is one solve per catalogue and a comparison of totals, never an average price.

Exact constraints on inexact numbers. Composition tables give values per 100 g raw; recipes are weighed raw and eaten cooked; yields vary. A band of 1,000–1,300 kcal is enforced to the kilocalorie on figures that carry ±10 % at best. I keep the model exact and put the tolerance in the checker that validates the plan afterwards, so a plan is never rejected for a difference the data cannot see. The arithmetic and the drift test are in N.14.

Optimal and unwanted. The plan is a minimum of what I wrote, not of what the person wants; the tell is a plan that scores well and gets rejected. Rejections are logged with the slot and the stated reason, and a reason that repeats is a term the objective did not have. Time limits belong here too: the incumbent at two seconds can sit 3 % from the bound, and a repair after a manual swap can end worse than the plan it repaired. Both are reported as numbers, gap and delta, rather than silently accepted, and a person's swap becomes a fixed variable, so that if it makes the week infeasible the ladder says which constraint bent to admit it.