Brief
The diet problem was one of the first problems ever solved by computer: find the cheapest set of foods that meets every nutrient requirement. It is a linear program. The cost is linear in the amounts you buy, and every rule, such as "at least 50 g of protein" or "at most 2,300 mg of sodium", is a linear inequality:
Each inequality cuts space in half, and the plans that survive every cut form the feasible region. That region is convex: the straight line between any two feasible plans is feasible too. Convexity is why these problems can be solved exactly. There are no false bottoms, so any local minimum is the global one. For a linear cost, the minimum sits at a corner of the region, and the simplex method walks from corner to corner to find it.
Lagrange multipliers tell you what each rule costs. At the optimum, where a constraint is tight, the cost gradient lines up with the constraint gradient: . The number is the price of that rule, the change in the best cost per extra unit of requirement. LP solvers call these shadow prices.
DATA · nutrition or price table
Objectives
Read-only. Log in to update progress.
VICTORY CONDITIONS
- Your simplex solver matches `scipy.optimize.linprog` on the full table, with optimal cost within 1e-6. Record your cost with `python tools/mlarena.py record BM-19 "<optimal cost>"`.
- Every constraint holds at your solution to within 1e-9, and your solver correctly reports infeasible and unbounded test problems.
- Your shadow prices agree with res.ineqlin.marginals, with a one-line meaning for each binding constraint.
Side quests
Terms in plain words
- Linear program (LP)
- Minimise a linear cost subject to linear inequality and equality constraints.
- Feasible region
- Every plan that satisfies all the constraints. For an LP it is a polygon, or a polytope in more dimensions.
- Convex
- A set is convex if the straight line between any two of its points stays inside it. In a convex problem, any local minimum is the global minimum.
- Lagrange multiplier
- The number λ attached to a constraint. At the optimum ∇f = λ∇g, and λ tells you how much the best cost changes if the constraint moves by one unit.
- Simplex method
- Walks from corner to corner of the feasible region, lowering the cost each time, until no neighbouring corner is cheaper.