The Diet Problem

Summary: The goal of the diet problem is to select a set of foods that will satisfy a set of daily nutritional requirement at minimum cost. The problem is formulated as a linear program where the objective is to minimize cost and the constraints are to satisfy the specified nutritional requirements. The diet problem constraints typically regulate the number of calories and the amount of vitamins, minerals, fats, sodium, and cholesterol in the diet. While the mathematical formulation is simple, the solution may not be palatable! The nutritional requirements can be met without regard for taste or variety, so consider the output before digging into a meal from an "optimal" menu!

Case Study Contents

History

The diet problem was one of the first optimization problems studied in the 1930s and 1940s. The problem was motivated by the Army's desire to minimize the cost of feeding GIs in the field while still providing a healthy diet. One of the early researchers to study the problem was George Stigler, who made an educated guess of an optimal solution using a heuristic method. His guess for the cost of an optimal diet was $39.93 per year (1939 prices). In the fall of 1947, Jack Laderman of the Mathematical Tables Project of the National Bureau of Standards used the newly developed simplex method to solve Stigler's model. As the first "large scale" computation in optimization, the linear program consisted of nine equations in 77 unknowns. It took nine clerks using hand-operated desk calculators 120 man days to solve for the optimal solution of $39.69. Stigler's guess was off by only $0.24 per year!

Back to the top

Problem Statement

Given a set of foods, along with the nutrient information for each food and the cost per serving of each food, the objective of the diet problem is to select the number of servings of each food to purchase (and consume) so as to minimize the cost of the food while meeting the specified nutritional requirements. Typically, the nutritional requirements are expressed as a minimum and a maximum allowable level for each nutritional component. Other constraints such a minimum and/or maximum number of servings may be included to improve the quality of the menu.

Consider the following simple example (from The Diet Problem: A WWW-based Interactive Case Study in Linear Programming). Suppose there are three foods available, corn, milk, and bread, and there are restrictions on the number of calories (between 2000 and 2250) and the amount of Vitamin A (between 5000 and 50,000). The first table lists, for each food, the cost per serving, the amount of Vitamin A per serving, and the number of calories per serving.

Food Cost per serving Vitamin A Calories
Corn $0.18 107 72
2% Milk $0.23 500 121
Wheat Bread $0.05 0 65

Suppose that the maximum number of servings is 10. Then, the optimal solution for the problem is 1.94 servings of corn, 10 servings of milk, and 10 servings of bread with a total cost of $3.15. The total amount of Vitamin A is 5208 and the total number of calories is 2000.

Back to the top

Diet Problem Solver

Click here or on the image to solve your own diet problems!

Back to the top

Mathematical Formulation

The Diet Problem can be formulated mathematically as a linear programming problem as shown below.

Sets
F = set of foods
N = set of nutrients

Parameters
\(a_{ij}\) = amount of nutrient \(j\) in food \(i\), \(\forall i \in F\), \(\forall j \in N\)
\(c_i\) = cost per serving of food \(i\), \(\forall i \in F\)
\(Fmin_i\) = minimum number of required servings of food \(i\), \(\forall i \in F\)
\(Fmax_i\) = maximum allowable number of servings of food \(i\), \(\forall i \in F\)
\(Nmin_j\) = minimum required level of nutrient \(j\), \(\forall j \in N\)
\(Nmax_j\) = maximum allowable level of nutrient \(j\), \(\forall j \in N\)

Variables
\(x_i\) = number of servings of food \(i\) to purchase/consume, \(\forall i \in F\)

Objective Function: Minimize the total cost of the food
Minimize \(\sum_{i \in F} c_i x_i\)

Constraint Set 1: For each nutrient \(j \in N\), at least meet the minimum required level.
\(\sum_{i \in F} a_{ij} x_i \geq Nmin_j, \forall j \in N\)

Constraint Set 2:For each nutrient \(j \in N\), do not exceed the maximum allowable level.
\(\sum_{i \in F} a_{ij} x_i \leq Nmax_j, \forall j \in N\)

Constraint Set 3:For each food \(i \in F\), select at least the minimum required number of servings.
\(x_i \geq Fmin_i, \forall i \in F\)

Constraint Set 4:For each food \(i \in F\), do not exceed the maximum allowable number of servings.
\(x_i \leq Fmax_i, \forall i \in F\)

To solve this linear programming problem, we can use one of the NEOS Server solvers in the Linear Programming category. Each LP solver has one or more input formats that it accepts. As an example, we provide an AMPL model for the simple example described above.

Back to the top

AMPL Implementation

############# model file #############
set F;
set N;

param a{F,N} >= 0;
param c{F} >= 0;
param Fmin{F} >= 0;
param Fmax{i in F} >= Fmin[i];
param Nmin{j in N} >= 0;
param Nmax{j in N} >= Nmax[j];

var x{i in F} >= Fmin[i],

minimize total_cost: sum {i in F} c[i]*x[i];

subject to nutritional_reqs{j in N}:
Nmin[j] <= sum {i in F} amt [i,j]*x[i] <= Nmax[j];

############# data file #############
data;
set F := corn, milk, bread;
set N := vitA, calories;

param: c Fmin Fmax :=
corn 0.18 0 10
milk 0.23 0 10
bread 0.05 0 10;

param: Nmin Nmax :=
vitA 5000 50000
calories 2000 2250;

param a: vitA calories :=
corn 107 72
milk 500 121
bread 0 65;

############# command file #############
solve;
display x;

Back to the top

Interpreting the Solution

Every linear program has associated with it another linear programming problem called the dual. One key application of duality theory -- the relationships between the primal problem and the dual problem -- is sensitivity analysis. Associated with each constraint in the primal problem is a dual variable, which represents in some sense the cost of having the constraint in the model. In the diet problem, there are two types of constraints, bounds on the number of servings for each food type and requirements on the allowable levels for each nutrient. Consider first the bounds on the number of servings for each food type. The table below shows the number of servings in the optimal solution and the associated dual variable value.

Food # Servings Dual Value
Corn 1.94 0
Milk 10 -0.073
Bread 10 -0.113

The variables for milk and bread are both at their upper bounds and have negative dual variable values, while the variable for corn is between its lower and upper bounds and has a zero dual variable value. A simple interpretation of this information is that the cost of the menu could be decreased if the upper bounds on the number of servings of milk and bread were increased. The cost of the menu would not change in response to an increase in the upper bound on the number of servings of corn. Modifying the AMPL data file to change Fmax[milk] to 11 and Fmax[bread] to 11 and solving again yields a solution with an objective function value of $2.99 and variable values of x[corn] = 0, x[milk] = 10.6198, and x[bread] = 11.

Consider now the two nutrient constraints on vitamin A and calories. The level of vitamin A (in the original solution) is 5208, which is between its minimum and maximum allowable levels, and therefore the corresponding dual variable values for both bounds are zero. The number of calories (in the original solution) is 2000, however, which is the minimum required. The corresponding dual variable value for the lower bound on the number of calories is 0.0025, which can be interpreted as the amount by which the objective function will decrease per unit of decrease in the bound. Therefore, modifying the AMPL data file to change Nmin[calories] to 1999 and solving again yields an optimal solution with an objective function value of $3.1475 and variable values of x[corn] = 1.93, x[milk] = 10, and x[bread] = 10. The objective function value decreased from $3.15 to $3.1475 as expected. Additional sensitivity analysis can be done to investigate the impacts of changing the cost coefficients as well as the \(a_{ij}\) parameter values.

For more information on linear programming, consult one of the many good references available, such as Introduction to Operations Research, 8th ed by Hillier and Lieberman or Introduction to Linear Optimization by Bertsimas and Tsitsiklis. The Linear Programming FAQ provides an extensive list of resources.

Back to the top

Acknowledgments

* The nutrition information was obtained from US Department of Agriculture National Nutrient Database for Standard Reference.
* The demo and description of this case study were originally created by Optimization Center at Northwestern University.
* The history of the diet problem was obtained from George Dantzig's 1990 article in Interfaces: G.B. Dantzig. The Diet Problem, Interfaces 20(4), 1990, 43-47.

Optimization Category (Linear Programing, Integer, MIP and etc.):