| The McDonald's Diet Problem | A Case Study in Optimization Using AMPL |
At most one drink per "meal", or 3 drinks for the day:
subject to OneDrinkPerMeal: 3 = Buy["Vanilla Shake"] + Buy["Chocolate Shake"] + Buy["Strawberry Shake"] + Buy["1% Lowfat Milk"] + Buy["Orange Juice"] + Buy["Coca-Cola (small)"] + Buy["Coca-Cola (medium)"] + Buy["Coca-Cola (large)"] + Buy["Diet Coke (small)"] + Buy["Diet Coke (medium)"] + Buy["Diet Coke (large)"] + Buy["Sprite (small)"] + Buy["Sprite (medium)"] + Buy["Sprite (large)"] + Buy["H-C Orange Drink (small)"] + Buy["H-C Orange Drink (medium)"] + Buy["H-C Orange Drink (large)"];At most one package of sauce for each 3 McNuggets:
subject to McNuggetsSauces: Buy["Hot Mustard Sauce"] + Buy["Barbeque Sauce"] + Buy["Sweet 'N Sour Sauce"] + Buy["Honey"] <= 2 * Buy["Chicken McNuggets (6 pcs)"] + 3 * Buy["Chicken McNuggets (9 pcs)"] + 6 * Buy["Chicken McNuggets (20 pcs)"];At most one topping and one dressing per salad:
subject to SaladToppings: Buy["Croutons"] + Buy["Bacon Bits"] <= Buy["Chef Salad"] + Buy["Chunky Chicken Salad"] + Buy["Garden Salad"] + Buy["Side Salad"]; subject to SaladDressings: Buy["Bleu Cheese Dressing"] + Buy["Ranch Dressing"] + Buy["1000 Island Dressing"] + Buy["Lite Vinaigrette Dressing"] + Buy["French Rdcd Cal Dressing"] <= Buy["Chef Salad"] + Buy["Chunky Chicken Salad"] + Buy["Garden Salad"] + Buy["Side Salad"];Calories from fat must be at most 30% of total calories:
subject to FatCaloriesLimit:
sum {j in FOOD} amt["CalFat",j] * Buy[j]
<= 0.3 * sum {j in FOOD} amt["Cal",j] * Buy[j];
We also make 2 of each food the default maximum:
param f_max {j in FOOD} >= f_min[j], default 2;
As before, we have to wait a long time for the solver to come back
with an integer solution -- almost 3 times as long as for our previous
run of cplex 3.0 without the new constraints. Sometimes adding
constraints can make an integer program easier to solve, though; it's
hard to predict in advance of trying. (By generating some additional
output, it's possible to show in this case that the optimal solution
is found in about 1/5 of the solver time. The rest is spent in
verifying that no better solution exists.)The extra constraints have pushed the cost up to $9.06, compared with $7.90 before. Notice that the calories from fat turn out to be only 26% of total calories, so that our extra constraint for this purpose wasn't really needed -- in this case; it might be an important constraint in other runs, with different data or constraints.
The diet looks better now. You might break it into three separate meals as:
| Meal 1 | Meal 2 | Meal 3 | |
|---|---|---|---|
| Cheerios | Cheeseburger | 2 Hamburgers | |
| Orange Juice | Side Salad | Chocolate Shake | |
| English Muffin | Croutons | ||
| Cinn Raisin Danish | H-C Orange (large) |
This is still probably not to your taste, though. What further ad hoc constraints would you add? How would you write them in AMPL?
stretto% ampl
ampl: model diet2.mod;
ampl: data diet2.dat;
ampl: option solver cplex;
ampl: option cplex_options 'timing 1';
ampl: solve;
CPLEX 3.0: timing 1
MIP Presolve modified 3 coefficients.
Reduced MIP has 16 rows, 64 columns, and 592 nonzeros.
Times (seconds):
Input = 0.0333333
Solve = 151.983
Output = 0.0166667
CPLEX 3.0: optimal integer solution within mipgap; objective 9.06
34830 simplex iterations
17742 branch-and-bound nodes
Objective = Total_Cost
ampl: option omit_zero_rows 1;
ampl: display Buy;
Buy [*] :=
Hamburger 2
Cheeseburger 1
'Side Salad' 1
'English Muffin' 1
Cheerios 1
'Cinnamon Raisin Danish' 1
'Chocolate Shake' 1
'Orange Juice' 1
'Coca-Cola (large)' 1
;
ampl: display n_min,Diet.body,n_max;
: n_min Diet.body n_max :=
Cal 2000 2255 Infinity
CalFat 0 590 Infinity
Fat 0 65 100
SatFat 0 23.5 30
Chol 0 225 375
Sodium 0 2805 3000
Carbo 350 353 375
Protein 55 68 Infinity
VitA 100 127 Infinity
VitC 100 171 Infinity
Calcium 100 104 Infinity
Iron 100 103 Infinity
;
Notice that the optimal solution is not quite the same as before: a large H-C Orange Drink has been substituted for a large Coca-Cola, and salad croutons have been added. This solution still satisfies all the constraints, however, and has the same cost of $9.06, so it's an equally optimal diet. In general there can be many optimal solutions, but a solver will return just one of them.
$ ampl
ampl: model diet2.mod;
ampl: data diet2.dat;
ampl: option solver osl;
ampl: option osl_options 'bbdisplay 2 bbdispfreq 100 timing 1';
OSL 1.2:
bbdisplay 2
bbdispfreq 100
timing 1
The primal algorithm has been chosen
Switching to Devex pricing--Success rate
Nodes Integer Simplex
Searched Soln's Iters Best Bound Gap
13 1 100 9.84 7.8289347 2.0e+00
100 1 332 9.84 7.940964 1.9e+00
169 2 550 9.34 8.0364143 1.3e+00
200 2 655 9.34 8.3701384 9.7e-01
300 2 905 9.34 8.4485473 8.9e-01
400 2 1186 9.34 8.4941215 8.5e-01
500 2 1434 9.34 8.5110731 8.3e-01
600 2 1719 9.34 8.5777599 7.6e-01
608 3 1739 9.33 8.5777599 7.5e-01
700 3 1985 9.33 8.5970025 7.3e-01
800 3 2293 9.33 8.6305918 7.0e-01
900 3 2556 9.33 8.6727391 6.6e-01
999 4 2822 9.06 8.7002899 3.6e-01
1000 4 2823 9.06 8.7002899 3.6e-01
1100 4 3064 9.06 8.7370094 3.2e-01
1200 4 3264 9.06 8.7477203 3.1e-01
1300 4 3467 9.06 8.7707548 2.9e-01
1400 4 3677 9.06 8.79675 2.6e-01
1500 4 3882 9.06 8.8190424 2.4e-01
1600 4 4074 9.06 8.8421262 2.2e-01
1700 4 4233 9.06 8.8471204 2.1e-01
1800 4 4423 9.06 8.8698095 1.9e-01
1900 4 4611 9.06 8.8923775 1.7e-01
2000 4 4788 9.06 8.9083237 1.5e-01
2100 4 4962 9.06 8.9181708 1.4e-01
2200 4 5127 9.06 8.9395922 1.2e-01
2300 4 5265 9.06 8.9508785 1.1e-01
2400 4 5411 9.06 8.9585433 1.0e-01
2500 4 5545 9.06 8.9704382 9.0e-02
2600 4 5669 9.06 8.9866515 7.3e-02
2700 4 5783 9.06 9.0288758 3.1e-02
2800 4 5885 9.06 9.0563103 3.7e-03
Times (seconds):
Input = 0.1
Solve = 98.8167
Output = 0
OSL 1.2: optimal solution; objective 9.06
5897 simplex iterations; 2807 branch-and-bound nodes
4 feasible integer solutions found
Objective = Total_Cost
ampl: option omit_zero_rows 1;
ampl: display Buy;
Buy [*] :=
Hamburger 2
Cheeseburger 1
'Side Salad' 1
Croutons 1
'English Muffin' 1
Cheerios 1
'Cinnamon Raisin Danish' 1
'Chocolate Shake' 1
'Orange Juice' 1
'Coca-Cola (large)' 1
;
ampl: display n_min,Diet.body,n_max;
: n_min Diet.body n_max :=
Cal 2000 2305 Infinity
CalFat 0 610 Infinity
Fat 0 67 100
SatFat 0 24 30
Chol 0 225 375
Sodium 0 2945 3000
Carbo 350 360 375
Protein 55 69 Infinity
VitA 100 127 Infinity
VitC 100 171 Infinity
Calcium 100 104 Infinity
Iron 100 103 Infinity
;
Getting the calories down to this level has increased the cost from $9.06 to $13.01. But are there cheaper meals with the same number of calories? In fact the cheapest such meal costs $9.89, and does contain some hamburgers, as you can show by setting n_max["Cal"] to 2000 and re-solving for the objective Total_Cost.
ampl: objective Nutr_Amt["Cal"];
ampl: solve;
OSL 1.2:
bbdisplay 2
bbdispfreq 100
timing 1
The primal algorithm has been chosen
Switching to Devex pricing--Success rate
Nodes Integer Simplex
Searched Soln's Iters Best Bound Gap
30 1 217 2040 2000 4.0e+01
100 1 770 2040 2000 4.0e+01
200 1 1565 2040 2000 4.0e+01
300 1 2018 2040 2000 4.0e+01
400 1 2684 2040 2000 4.0e+01
500 1 3263 2040 2000 4.0e+01
600 1 3881 2040 2000 4.0e+01
700 1 4638 2040 2000 4.0e+01
800 1 5379 2040 2000 4.0e+01
900 1 6004 2040 2000 4.0e+01
1000 1 6548 2040 2000 4.0e+01
1100 1 7197 2040 2000 4.0e+01
1200 1 7921 2040 2000 4.0e+01
1220 2 8049 2005 2000 5.0e+00
1300 2 8491 2005 2000 5.0e+00
1400 2 9071 2005 2000 5.0e+00
1500 2 9615 2005 2000 5.0e+00
1600 2 10365 2005 2000 5.0e+00
1700 2 10919 2005 2000 5.0e+00
1800 2 11615 2005 2000 5.0e+00
1847 3 11910 2000 2000 1.7e-11
Times (seconds):
Input = 0.0666667
Solve = 80.5833
Output = 0
OSL 1.2: optimal solution; objective 2000
11910 simplex iterations; 1847 branch-and-bound nodes
3 feasible integer solutions found
ampl: display Total_Cost;
Total_Cost = 13.95
ampl: display Buy;
Buy [*] :=
'Side Salad' 2
'English Muffin' 2
Cheerios 1
Wheaties 2
'Cheese Danish' 1
'Lowfat Frozen Yogurt Cone' 2
'Vanilla Shake' 1
'1% Lowfat Milk' 1
'Coca-Cola (large)' 1
;
ampl: display n_min,Diet.body,n_max;
: n_min Diet.body n_max :=
Cal 2000 2000 Infinity
CalFat 0 405 Infinity
Fat 0 44 100
SatFat 0 16.5 30
Chol 0 175 375
Sodium 0 2110 3000
Carbo 350 350 375
Protein 55 57 Infinity
VitA 100 247 Infinity
VitC 100 103 Infinity
Calcium 100 133 Infinity
Iron 100 100 Infinity
;
ampl: let n_max["Cal"] := 2000;
ampl: objective Total_Cost;
ampl: solve;
OSL 1.2:
bbdisplay 2
bbdispfreq 100
timing 1
The primal algorithm has been chosen
Switching to Devex pricing--Growth of factorization
Nodes Integer Simplex
Searched Soln's Iters Best Bound Gap
100 0 407
200 0 836
295 1 1235 15.03 8.3655379 6.7e+00
300 1 1264 15.03 8.3655379 6.7e+00
342 2 1428 10.55 8.3728753 2.2e+00
400 2 1675 10.55 8.5033072 2.0e+00
500 2 2103 10.55 8.7265134 1.8e+00
600 2 2492 10.55 8.8632278 1.7e+00
617 3 2557 9.89 8.8632691 1.0e+00
700 3 2840 9.89 9.0093739 8.8e-01
800 3 3190 9.89 9.1194697 7.7e-01
900 3 3511 9.89 9.1975834 6.9e-01
1000 3 3812 9.89 9.2400934 6.5e-01
1100 3 4102 9.89 9.313657 5.8e-01
1200 3 4352 9.89 9.3763781 5.1e-01
1300 3 4587 9.89 9.4245236 4.7e-01
1400 3 4824 9.89 9.4593329 4.3e-01
1500 3 5066 9.89 9.5240073 3.7e-01
1600 3 5252 9.89 9.5792083 3.1e-01
1700 3 5457 9.89 9.6046549 2.9e-01
1800 3 5665 9.89 9.6650165 2.2e-01
1900 3 5842 9.89 9.6918035 2.0e-01
2000 3 6007 9.89 9.7396577 1.5e-01
2100 3 6157 9.89 9.7876888 1.0e-01
2200 3 6292 9.89 9.8486469 4.1e-02
Times (seconds):
Input = 0.0833333
Solve = 83.1167
Output = 0.0166667
OSL 1.2: optimal solution; objective 9.89
6388 simplex iterations; 2279 branch-and-bound nodes
3 feasible integer solutions found
ampl: display Buy;
Buy [*] :=
Hamburger 1
Cheeseburger 1
'Garden Salad' 1
Croutons 1
'Lite Vinaigrette Dressing' 1
Cheerios 1
Wheaties 2
'Strawberry Shake' 2
'H-C Orange Drink (large)' 1
;
ampl: display n_min,Diet.body,n_max;
: n_min Diet.body n_max :=
Cal 2000 2000 2000
CalFat 0 380 Infinity
Fat 0 41 100
SatFat 0 15.5 30
Chol 0 200 375
Sodium 0 2730 3000
Carbo 350 350 375
Protein 55 63 Infinity
VitA 100 165 Infinity
VitC 100 106 Infinity
Calcium 100 110 Infinity
Iron 100 112 Infinity
;
Return to the AMPL examples page.