Diet Problem & Sensitivity Analysis (LP Duals & Slacks)

Problem Class	Solver	Key APIs	Links
Linear Programming (LP)	HiGHS (default)	m.continuous(), m.constraint(), expr (dot), minimize	Open in Playground Source Code

When solving a Linear Programming model, the optimal variable values (var.value) are only half the story. In practice, decision-makers need to know:

1. Bottlenecks (constr.dual — Shadow Price): Which minimum requirements are actively driving up the total cost, and by how much per unit?
2. Surpluses (constr.slack): Which constraints have room to spare?
3. Reduced Costs (var.reducedCost): For items not selected in the optimal plan, how much cheaper would they need to become before entering the solution?

Problem Inputs

We choose daily servings ($0 \le x_i \le 4$) among 6 food items to meet 4 daily nutritional minimums (Calories >= 2000 kcal, Protein >= 105 g, Calcium >= 1000 mg, Iron >= 18 mg) at minimum cost:

Food Item	Cost / Serving	Calories (kcal)	Protein (g)	Calcium (mg)	Iron (mg)	Max Servings
Oats	$0.60	150	5	20	1.8	4.0
Chicken	$2.40	220	32	15	1.2	4.0
Eggs	$0.80	140	12	50	1.7	4.0
Milk	$0.90	120	8	280	0.1	4.0
Spinach	$1.50	40	4	120	3.5	4.0
Salmon	$3.60	200	25	20	0.8	4.0

Implementation in WaSHI

import { Model, minimize, expr } from "@ohtaman/washi";

const foods = [
  { name: "Oats",    cost: 0.60, calories: 150, protein: 5,  calcium: 20,  iron: 1.8 },
  { name: "Chicken", cost: 2.40, calories: 220, protein: 32, calcium: 15,  iron: 1.2 },
  { name: "Eggs",    cost: 0.80, calories: 140, protein: 12, calcium: 50,  iron: 1.7 },
  { name: "Milk",    cost: 0.90, calories: 120, protein: 8,  calcium: 280, iron: 0.1 },
  { name: "Spinach", cost: 1.50, calories: 40,  protein: 4,  calcium: 120, iron: 3.5 },
  { name: "Salmon",  cost: 3.60, calories: 200, protein: 25, calcium: 20,  iron: 0.8 },
];

async function runDietSensitivity() {
  const m = new Model("DietSensitivity");

  // Continuous servings per day (0 to 4 servings max per food)
  const srv = m.continuous(foods.map((f) => f.name), { lb: 0, ub: 4 });

  const costs = Object.fromEntries(foods.map((f) => [f.name, f.cost]));
  const cals  = Object.fromEntries(foods.map((f) => [f.name, f.calories]));
  const prots = Object.fromEntries(foods.map((f) => [f.name, f.protein]));
  const calcs = Object.fromEntries(foods.map((f) => [f.name, f.calcium]));
  const irons = Object.fromEntries(foods.map((f) => [f.name, f.iron]));

  // Objective: Minimize total daily cost via dot() inside expr
  m.objective(minimize(expr`dot(${costs}, ${srv})`));

  // Nutritional constraints defined declaratively with expr and constraint()
  const nutConstraints = [
    m.constraint(expr`dot(${cals}, ${srv}) >= 2000`, "min_calories"),
    m.constraint(expr`dot(${prots}, ${srv}) >= 105`,  "min_protein"),
    m.constraint(expr`dot(${calcs}, ${srv}) >= 1000`, "min_calcium"),
    m.constraint(expr`dot(${irons}, ${srv}) >= 18`,   "min_iron"),
  ];

  const status = await m.solve();

  console.log(`Status: ${status}, Minimum Daily Cost: $${m.objectiveValue?.toFixed(2)}`);
  console.log("--- Food Servings & Reduced Costs ---");
  for (const f of foods) {
    const v = srv[f.name];
    console.log(`  ${f.name.padEnd(8)}: value=${v.value?.toFixed(2)}, reducedCost=${v.reducedCost?.toFixed(4)}`);
  }
  console.log("--- Nutritional Constraints (Dual & Slack) ---");
  for (const c of nutConstraints) {
    console.log(`  ${c.name.padEnd(13)}: dual=$${c.dual?.toFixed(4)}, slack=${Math.abs(c.slack ?? 0).toFixed(2)}`);
  }
}

runDietSensitivity();

Open in Playground →

Interpretation of Results

• Bottleneck constraints (slack == 0, dual > 0): Calories (2000 kcal) and Iron (18 mg) are tight at their lower bounds. Increasing the daily Iron requirement by 1 mg increases the minimum daily diet cost by $0.3241.
• Constraints with surplus (slack > 0, dual == 0): Protein (+46.46 g surplus) and Calcium (+483.02 mg surplus) are already exceeded with room to spare, so their shadow prices are $0.
• Reduced cost at lower bound (Salmon): Unselected Salmon (0.00 servings) has a reduced cost of +1.5125, meaning its price per serving would need to drop by at least $1.51 before it enters the optimal daily menu.
• Negative reduced cost at upper bound (Oats, Eggs): Both Oats (reducedCost = -0.2581) and Eggs (reducedCost = -0.0887) are pinned against their upper serving cap (ub = 4.0). In a minimization LP, a negative reduced cost on an upper-bounded variable tells you how much the total objective would decrease per unit increase in ub—raising the daily cap on Oats from 4 to 5 servings would save $0.26/day.
• Basis stability range: Shadow prices (dual) and reduced costs (reducedCost) represent local marginal rates of change within the current optimal simplex basis. If a right-hand side or bound changes enough to trigger a basis change (for example, once another variable hits its bound), the marginal rate shifts to a new piece of the piecewise-linear optimal cost curve.