∇ProvenDecisions
Ctrl K

Diet problem as a linear program in Python: cheapest diet, solved and checked

Articles · 2026-11-20

The diet problem is a classic first example of linear programming: pick amounts of a few foods so that nutrition needs are met at the lowest cost. This article solves a small version in Python, then checks the answer two ways: every rule is satisfied, and no cheaper diet can exist.

The problem

Three foods are available: oats, milk and beans. Each has a price and a nutrition profile per serving.

Food Cost ($/serving) Protein (g/serving) Calcium (% daily value/serving) Iron (% daily value/serving)
Oats 0.30 5 1 4
Milk 0.25 8 30 0
Beans 0.50 9 4 3

A day needs at least:

Find the cheapest diet. We assume servings can be fractional (1.875 servings is fine).

The model in words

The model in math

minimize   0.30*oats + 0.25*milk + 0.50*beans     # total daily cost, in dollars
subject to
  5*oats + 8*milk + 9*beans  >= 40                # protein: at least 40 grams per day
  1*oats + 30*milk + 4*beans >= 60                # calcium: at least 60% of daily value
  4*oats + 0*milk + 3*beans  >= 20                # iron: at least 20% of daily value
  oats, milk, beans >= 0                          # no negative servings

# oats  = servings of oats per day  (servings)
# milk  = servings of milk per day  (servings)
# beans = servings of beans per day (servings)

Everything is a straight-line (linear) function of the three unknowns, so this is a linear program (LP). That is a good case: a solver can find the exact optimum and also give a certificate that it is the best.

The code

This uses cvxpy with the HiGHS solver. Install with pip install cvxpy highspy if needed.

import cvxpy as cp

# Decision variables: servings per day of each food (servings)
oats = cp.Variable(name="oats")
milk = cp.Variable(name="milk")
beans = cp.Variable(name="beans")

# Objective: total daily cost in dollars
cost = 0.30 * oats + 0.25 * milk + 0.50 * beans

constraints = [
    5 * oats + 8 * milk + 9 * beans >= 40,    # protein, grams
    1 * oats + 30 * milk + 4 * beans >= 60,   # calcium, % of daily value
    4 * oats + 0 * milk + 3 * beans >= 20,    # iron, % of daily value
    oats >= 0,                                # no negative servings
    milk >= 0,
    beans >= 0,
]

prob = cp.Problem(cp.Minimize(cost), constraints)
prob.solve(solver=cp.HIGHS)

print(prob.status, prob.value)

The solver reports status optimal and a cost of 1.96875 (up to tiny floating-point rounding).

The answer

The cheapest diet is:

The total cost is $1.96875 per day, about $1.97.

Beans never make it into the diet. They cost the most per serving ($0.50), and the other two foods cover the needs more cheaply.

How to check it

A solver says "optimal", but you should not have to take that on faith. Two checks make the answer trustworthy.

Check 1: every rule is satisfied

Plug the solution into each constraint.

cost     = 0.30*5 + 0.25*1.875 + 0.50*0
         = 1.50 + 0.46875 + 0
         = 1.96875 dollars per day

protein  = 5*5 + 8*1.875 + 9*0
         = 25 + 15 + 0
         = 40 grams            >= 40   OK (exactly met)

calcium  = 1*5 + 30*1.875 + 4*0
         = 5 + 56.25 + 0
         = 61.25 % daily value >= 60   OK (1.25 to spare)

iron     = 4*5 + 0*1.875 + 3*0
         = 20 % daily value    >= 20   OK (exactly met)

oats = 5, milk = 1.875, beans = 0      all >= 0   OK

All six rules (three nutrition minimums, three non-negativity rules) hold, with a largest violation of 0. Protein and iron are met exactly, so they are the "tight" rules. Calcium has a little slack.

Check 2: no cheaper diet exists (the dual)

Feasible is not the same as best. For an LP, the proof of optimality comes from the dual problem.

The idea: give each nutrition rule a "price" per unit of requirement. Call them y_protein (dollars per gram), y_calcium and y_iron (dollars per % of daily value). Choose prices so that, for every food, the value of the nutrients in one serving does not exceed that food's actual cost. Then any diet that meets the requirements must cost at least 40*y_protein + 60*y_calcium + 20*y_iron. This gives a lower bound on cost.

Calcium has slack in our solution, so its price is 0. That leaves two prices to find. Oats and milk are both used (above zero), so their price conditions must hold with equality:

milk:  8*y_protein + 0*y_iron = 0.25      # value of a milk serving equals its cost
       y_protein = 0.25 / 8 = 0.03125     # dollars per gram of protein

oats:  5*y_protein + 4*y_iron = 0.30      # value of an oats serving equals its cost
       4*y_iron = 0.30 - 5*0.03125 = 0.30 - 0.15625 = 0.14375
       y_iron = 0.14375 / 4 = 0.0359375   # dollars per % of daily value of iron

Now confirm these prices are valid for beans, which is not used:

beans: 9*0.03125 + 3*0.0359375 = 0.28125 + 0.1078125 = 0.3890625
       0.3890625 <= 0.50          # beans cost more than their nutrient value, OK

The prices are valid, so they give a lower bound on any feasible diet's cost:

lower bound = 40*0.03125 + 60*0 + 20*0.0359375
            = 1.25 + 0 + 0.71875
            = 1.96875 dollars per day

The lower bound is 1.96875 and our diet costs 1.96875, so the gap is 0. No diet can cost less. The solver's own dual check agrees: dual objective 1.96875, gap 0.

The prices also have a practical meaning. One extra gram of protein requirement adds about $0.03125 to the daily cost. One extra % of iron requirement adds about $0.0359375. Extra calcium costs nothing at the margin, because the diet already overshoots it.

Takeaway

If you want to try this on your own problem, typed as math, LaTeX, a photo or spoken, this example is solved and checked in ProvenDecisions: https://proven-decisions.ai/examples/diet-problem

This article was written with AI assistance; every number in it comes from the solver run shown above.

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: