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

3. THE WHOLE NUMBER SOLUTION

Looking again at the original diet solution, we recall that buying 4.38525 quarter pounders with cheese can be hard to arrange.

   stretto% ampl
   
   ampl: model diet1.mod;
   ampl: data diet1.dat;
   
   ampl data: solve;
   MINOS 5.4: ignoring integrality of 9 variables
   MINOS 5.4: optimal solution found.
   8 iterations, objective 14.8557377
   
   ampl: display Buy;
   
   Buy [*] :=
   'Quarter Pounder w/ Cheese'  4.38525
     'McLean Deluxe w/ Cheese'  0
                     'Big Mac'  0
                  Filet-O-Fish  0
           'McGrilled Chicken'  0
                'Fries, small'  6.14754
            'Sausage McMuffin'  0
              '1% Lowfat Milk'  3.42213
                'Orange Juice'  0
   ;
   
   ampl: display n_min,Diet.body,n_max;
   
   :        n_min  Diet.body    n_max      :=
   Cal       2000   3965.37    Infinity
   Carbo      350    350            400
   Protein     55    172.029   Infinity
   VitA       100    100       Infinity
   VitC       100    132.213   Infinity
   Calc       100    234.221   Infinity
   Iron       100    100       Infinity
   ;

One way to deal with the fractions would be to buy the next-highest whole number amount, then leave the appropriate fractional amount uneaten. That drives the cost up from $14.85 to $16.99, however.

   ampl: let {j in FOOD} Buy[j] := ceil(Buy[j]);
   
   ampl: display Total_Cost;
   Total_Cost = 16.99

A more economical approach would be to round the amount of each food to the nearest whole number. In this case, all the amounts happen to get rounded down, so the cost is less. The requirements for carbohydrates, vitamin A and iron fail to be met, however.

   ampl: solve;
   MINOS 5.4: ignoring integrality of 9 variables
   MINOS 5.4: optimal solution found.
   2 iterations, objective 14.8557377
   Objective = Total_Cost
   
   ampl: let {j in FOOD} Buy[j] := round(Buy[j]);
   
   ampl: display Total_Cost;
   Total_Cost = 13.78
   
   ampl: display Buy;
   
   Buy [*] :=
   'Quarter Pounder w/ Cheese'  4
     'McLean Deluxe w/ Cheese'  0
                     'Big Mac'  0
                  Filet-O-Fish  0
           'McGrilled Chicken'  0
                'Fries, small'  6
            'Sausage McMuffin'  0
              '1% Lowfat Milk'  3
                'Orange Juice'  0
   ;
   
   ampl: display n_min,Diet.body,n_max;
   
   :        n_min Diet.body    n_max      :=
   Cal       2000    3690     Infinity
   Carbo      350     328          375
   Protein     55     157     Infinity
   VitA       100      90     Infinity
   VitC       100     126     Infinity
   Calc       100     210     Infinity
   Iron       100      92     Infinity
   ;

Is there a more satisfactory way to adjust the fractional values? We can switch to a different solver that honors the declaration "var Buy {j in FOOD} integer ..." in the model. We see that the best solution in integers is only about 20 cents more expensive than the fractional solution, but it differs from the fractional solution in a way that would be hard to predict: quarter pounders are rounded down, milk is rounded up, fries are dropped from 6.1 down to 5, and one filet-o-fish is added to the diet.

   ampl: option solver cplex;
   
   ampl: solve;
   CPLEX 2.1: optimal integer solution; objective 15.05
   129 simplex iterations
   112 branch-and-bound nodes
   Objective = Total_Cost
   
   ampl: display Buy;
   
   Buy [*] :=
   'Quarter Pounder w/ Cheese'  4
     'McLean Deluxe w/ Cheese'  0
                     'Big Mac'  0
                  Filet-O-Fish  1
           'McGrilled Chicken'  0
                'Fries, small'  5
            'Sausage McMuffin'  0
              '1% Lowfat Milk'  4
                'Orange Juice'  0
   ;
   
   ampl: display n_min,Diet.body,n_max;
   
   :        n_min Diet.body    n_max      :=
   Cal       2000    3950     Infinity
   Carbo      350     352          375
   Protein     55     177     Infinity
   VitA       100     102     Infinity
   VitC       100     115     Infinity
   Calc       100     255     Infinity
   Iron       100     100     Infinity
   ;

Now you can go back and solve all the other cases in integers. Here's a table of the results you should get. The yes-yes row is arguably the most realistic, though also the most expensive; how much difference is there between the minimum-cost and minimum-calorie diets in that case?

                                       min        min
      varied?  integer?     calories  cost     calories  cost
   
         no       no          3965   14.86       2467   16.75
         no      yes          3950   15.05       2500   17.16
        yes       no          3798   16.77       3488   17.25
        yes      yes          3630   17.04       3530   17.49


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.