The McDonald's Diet Problem A Case Study in Optimization Using AMPL

## 5. SOME AD HOC CONSTRAINTS

Based on a knowledge of McDonalds and of human eating habits, we can add some special constraints that will tend to provide a more acceptable solution. Here are some possibilities, described first in words and then in AMPL:

At most one drink per "meal", or 3 drinks for the day:

```	subject to OneDrinkPerMeal:

3 = Buy["Vanilla Shake"] +
Buy["1% Lowfat Milk"] +
Buy["Diet Coke (small)"] +
Buy["Diet Coke (medium)"] +
Buy["Diet Coke (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"] +

<= 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["Bleu Cheese Dressing"] +
Buy["1000 Island Dressing"] +
Buy["Lite Vinaigrette Dressing"] +
Buy["French Rdcd Cal Dressing"]

```
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;

Hamburger  2
Cheeseburger  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
;
```

Here's the same thing run using OSL on the workstation lab. Here it's somewhat faster than CPLEX 3.0 (at least with CPLEX's default settings).

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;

Hamburger  2
Cheeseburger  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
;
```

Finally, what does a low-calorie McDonald's diet look like, subject to our ad hoc constraints? We solve again, with the objective changed to total calories. The solution has only 2000 calories, that minimum that we've set. But there are no hamburgers of any kind in it.

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

'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

Hamburger  1
Cheeseburger  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
;
```