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!
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!
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.
Diet Problem Solver
The objective of the diet problem is to select a set of foods that will satisfy a set of daily nutritional requirements at minimum cost. To create your own optimized menu, select the foods that you would like to consider in your menu and specify the nutritional constraints that you would like to satisfy. You might be surprised at the contents of an optimized menu!
| Enter your email address if you want the solver solution log: | |
The solution will output in a pop-up window. Please allow pop-ups to ensure it appears correctly. |
|
Food Selection
- Mark the checkbox next to each food that you would like to consider in your menu. Note that you are more likely to get a solution if you select more food choices.
- Edit the "Min" and "Max" values if you would like to change the defaults for the number of servings of each food from Min = 0 and Max = 10.
Nutritional Requirements
- Unselect the checkbox next to any nutrients that you do not want to consider.
- Edit the "Min" and "Max" values for the nutrient levels if you would like to change them from their defaults.
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.
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], <= Fmax[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;
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.
Acknowledgments
* The nutrition information was obtained from USDA Ag Data Commons.
* 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.