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["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
   ;


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


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



Comments or questions?
Write to info@ampl.com or use our comment form.

Return to the AMPL examples page.

Return to the AMPL home page.


LAST MODIFIED 27 MARCH 1996 BY 4er.