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:
- 40 grams of protein
- 60% of the daily value of calcium
- 20% of the daily value of iron
Find the cheapest diet. We assume servings can be fractional (1.875 servings is fine).
The model in words
- Decisions: how many servings per day of oats, milk and beans.
- Goal: make the total daily cost, in dollars, as small as possible.
- Rules: total protein, total calcium and total iron must each reach the daily minimum. You cannot eat a negative number of servings.
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:
- Oats: 5 servings per day
- Milk: 1.875 servings per day
- Beans: 0 servings per day
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
- The diet problem is a linear program: a linear cost, linear nutrition rules, and non-negative amounts.
- In cvxpy, the model is a direct translation of the math, and
prob.solve(solver=cp.HIGHS)handles it. - Do not stop at "optimal". Check each rule by hand, then use the dual to prove nothing cheaper exists. Here the primal cost and the dual bound are both 1.96875, so the gap is 0.
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?ref=devto
This article was written with AI assistance; every number in it comes from the solver run shown above.
Top comments (0)