/* STIGLER, original Stigler's 1939 diet problem */

/* The Stigler Diet is an optimization problem named for George Stigler,

   a 1982 Nobel Laureate in economics, who posed the following problem:

   For a moderately active man weighing 154 pounds, how much of each of

   77 foods should be eaten on a daily basis so that the man's intake of

   nine nutrients will be at least equal to the recommended dietary

   allowances (RDSs) suggested by the National Research Council in 1943,

   with the cost of the diet being minimal?

   The nutrient RDAs required to be met in Stigler's experiment were

   calories, protein, calcium, iron, vitamin A, thiamine, riboflavin,

   niacin, and ascorbic acid. The result was an annual budget allocated

   to foods such as evaporated milk, cabbage, dried navy beans, and beef

   liver at a cost of approximately $0.11 a day in 1939 U.S. dollars.

   While the name "Stigler Diet" was applied after the experiment by

   outsiders, according to Stigler, "No one recommends these diets for

   anyone, let alone everyone." The Stigler diet has been much ridiculed

   for its lack of variety and palatability, however his methodology has

   received praise and is considered to be some of the earliest work in

   linear programming.

   The Stigler diet question is a linear programming problem. Lacking

   any sophisticated method of solving such a problem, Stigler was

   forced to utilize heuristic methods in order to find a solution. The

   diet question originally asked in which quantities a 154 pound male

   would have to consume 77 different foods in order to fulfill the

   recommended intake of 9 different nutrients while keeping expense at

   a minimum. Through "trial and error, mathematical insight and

   agility," Stigler was able to eliminate 62 of the foods from the

   original 77 (these foods were removed based because they lacked

   nutrients in comparison to the remaining 15). From the reduced list,

   Stigler calculated the required amounts of each of the remaining 15

   foods to arrive at a cost-minimizing solution to his question.

   According to Stigler's calculations, the annual cost of his solution

   was $39.93 in 1939 dollars. When corrected for inflation using the

   consumer price index, the cost of the diet in 2005 dollars is

   $561.43. The specific combination of foods and quantities is as

   follows:

   Stigler's 1939 Diet

   Food             Annual Quantities Annual Cost

   ---------------- ----------------- -----------

   Wheat Flour           370 lb.         $13.33

   Evaporated Milk        57 cans          3.84

   Cabbage               111 lb.           4.11

   Spinach                23 lb.           1.85

   Dried Navy Beans      285 lb.          16.80

   ----------------------------------------------

   Total Annual Cost                     $39.93

   The 9 nutrients that Stigler's diet took into consideration and their

   respective recommended daily amounts were:

   Table of nutrients considered in Stigler's diet

   Nutrient                  Daily Recommended Intake

   ------------------------- ------------------------

   Calories                       3,000 Calories

   Protein                           70 grams

   Calcium                           .8 grams

   Iron                              12 milligrams

   Vitamin A                      5,000 IU

   Thiamine (Vitamin B1)            1.8 milligrams

   Riboflavin (Vitamin B2)          2.7 milligrams

   Niacin                            18 milligrams

   Ascorbic Acid (Vitamin C)         75 milligrams

   Seven years after Stigler made his initial estimates, the development

   of George Dantzig's Simplex algorithm made it possible to solve the

   problem without relying on heuristic methods. The exact value was

   determined to be $39.69 (using the original 1939 data). Dantzig's

   algorithm describes a method of traversing the vertices of a polytope

   of N+1 dimensions in order to find the optimal solution to a specific

   situation.

   (From Wikipedia, the free encyclopedia.) */

/* Translated from GAMS by Andrew Makhorin <mao@gnu.org>.

   For the original GAMS model stigler1939.gms see [3].

   References:

   1. George J. Stigler, "The Cost of Subsistence," J. Farm Econ. 27,

      1945, pp. 303-14.

   2. National Research Council, "Recommended Daily Allowances," Reprint

      and Circular Series No. 115, January, 1943.

   3. Erwin Kalvelagen, "Model building with GAMS," Chapter 2, "Building

      linear programming models," pp. 128-34. */

set C;

/* commodities */

check card(C) = 77;

/* there must be 77 commodities */

set N;

/* nutrients */

param data{c in C, {"price", "weight"} union N};

/* nutritive values per dollar of expenditure */

param allowance{n in N};

/* recommended daily allowance for a moderately active man */

var x{c in C}, >= 0;

/* dollars of food to be purchased daily */

s.t. nb{n in N}: sum{c in C} data[c,n] * x[c] >= allowance[n];

/* nutrient balance */

minimize cost: sum{c in C} x[c];

/* total food bill */

solve;

param days := 365.25;

/* days in a year */

param commodity{c in C}, symbolic;

param unit{c in C}, symbolic;

printf "\n";

printf "MINIMUM COST ANNUAL DIET\n";

printf "\n";

printf "        Commodity            Unit     Quantity     Cost   \n";

printf "------------------------- ---------- ---------- ----------\n";

printf{c in C: x[c] != 0} "%-25s %10s %10.2f   $%7.2f\n", commodity[c],

   unit[c], 100 * days * x[c] / data[c,"price"], days * x[c];

printf "                                         -----------------\n";

printf "                                         Total:   $%7.2f\n",

   days * sum{c in C} x[c];

printf "\n";

data;

param : C :    commodity                   unit :=

flour          "Wheat Flour (Enriched)"    "10 lb."

macaroni       "Macaroni"                  "1 lb."

cereal         "Wheat Cereal (Enriched)"   "28 oz."

cornflakes     "Corn Flakes"               "8 oz."

cornmeal       "Corn Meal"                 "1 lb."

grits          "Hominy Grits"              "24 oz."

rice           "Rice"                      "1 lb."

oats           "Rolled Oats"               "1 lb."

whitebread     "White Bread (Enriched)"    "1 lb."

wheatbread     "Whole Wheat Bread"         "1 lb."

ryebread       "Rye Bread"                 "1 lb."

poundcake      "Pound Cake"                "1 lb."

crackers       "Soda Crackers"             "1 lb."

milk           "Milk"                      "1 qt."

evapmild       "Evaporated Milk (can)"     "14.5 oz."

butter         "Butter"                    "1 lb."

margarine      "Oleomargarine"             "1 lb."

eggs           "Eggs"                      "1 doz."

cheese         "Cheese (Cheddar)"          "1 lb."

cream          "Cream"                     "1/2 pt."

peanutbutter   "Peanut Butter"             "1 lb."

mayonnaise     "Mayonnaise"                "1/2 pt."

crisco         "Crisco"                    "1 lb."

lard           "Lard"                      "1 lb."

sirloinsteak   "Sirloin Steak"             "1 lb."

roundsteak     "Round Steak"               "1 lb."

ribroast       "Rib Roast"                 "1 lb."

chuckroast     "Chuck Roast"               "1 lb."

plate          "Plate"                     "1 lb."

liver          "Liver (Beef)"              "1 lb."

lambleg        "Leg of Lamb"               "1 lb."

lambchops      "Lamb Chops (Rib)"          "1 lb."

porkchops      "Pork Chops"                "1 lb."

porkroast      "Pork Loin Roast"           "1 lb."

bacon          "Bacon"                     "1 lb."

ham            "Ham - smoked"              "1 lb."

saltpork       "Salt Pork"                 "1 lb."

chicken        "Roasting Chicken"          "1 lb."

veal           "Veal Cutlets"              "1 lb."

salmon         "Salmon, Pink (can)"        "16 oz."

apples         "Apples"                    "1 lb."

bananas        "Bananas"                   "1 lb."

lemons         "Lemons"                    "1 doz."

oranges        "Oranges"                   "1 doz."

greenbeans     "Green Beans"               "1 lb."

cabbage        "Cabbage"                   "1 lb."

carrots        "Carrots"                   "1 bunch"

celery         "Celery"                    "1 stalk"

lettuce        "Lettuce"                   "1 head"

onions         "Onions"                    "1 lb."

potatoes       "Potatoes"                  "15 lb."

spinach        "Spinach"                   "1 lb."

sweetpotato    "Sweet Potatoes"            "1 lb."

peaches        "Peaches (can)"             "No. 2 1/2"

pears          "Pears (can)"               "No. 2 1/2"

pineapple      "Pineapple (can)"           "No. 2 1/2"

asparagus      "Asparagus (can)"           "No. 2"

cannedgrbn     "Grean Beans (can)"         "No. 2"

porkbeans      "Pork and Beans (can)"      "16 oz."

corn           "Corn (can)"                "No. 2"

peas           "Peas (can)"                "No. 2"

tomatoes       "Tomatoes (can)"            "No. 2"

tomatosoup     "Tomato Soup (can)"         "10 1/2 oz."

driedpeach     "Peaches, Dried"            "1 lb."

prunes         "Prunes, Dried"             "1 lb."

raisins        "Raisins, Dried"            "15 oz."

driedpeas      "Peas, Dried"               "1 lb."

limabeans      "Lima Beans, Dried"         "1 lb."

navybeans      "Navy Beans, Dried"         "1 lb."

coffee         "Coffee"                    "1 lb."

tea            "Tea"                       "1/4 lb."

cocoa          "Cocoa"                     "8 oz."

chocolate      "Chocolate"                 "8 oz."

sugar          "Sugar"                     "10 lb."

cornsirup      "Corn Sirup"                "24 oz."

molasses       "Molasses"                  "18 oz."

stawberry      "Strawberry Preserve"       "1 lb."

;

set N :=

calories       /* Calories, unit = 1000 */

protein        /* Protein, unit = grams */

calcium        /* Calcium, unit = grams */

iron           /* Iron, unit = milligrams */

vitaminA       /* Vitamin A, unit = 1000 International Units */

thiamine       /* Thiamine, Vit. B1, unit = milligrams */

riboflavin     /* Riboflavin, Vit. B2, unit = milligrams */

niacin         /* Niacin (Nicotinic Acid), unit = milligrams */

ascorbicAcid   /* Ascorbic Acid, Vit. C, unit = milligrams */

;

param data

:             price   weight calories protein  calcium   iron :=

#            aug. 15  edible

#             1939    per $1

#           (cents)   (grams) (1000)  (grams)  (grams)   (mg.)

flour         36.0    12600    44.7     1411     2.0      365

macaroni      14.1     3217    11.6      418      .7       54

cereal        24.2     3280    11.8      377    14.4      175

cornflakes     7.1     3194    11.4      252      .1       56

cornmeal       4.6     9861    36.0      897     1.7       99

grits          8.5     8005    28.6      680      .8       80

rice           7.5     6048    21.2      460      .6       41

oats           7.1     6389    25.3      907     5.1      341

whitebread     7.9     5742    15.6      488     2.5      115

wheatbread     9.1     4985    12.2      484     2.7      125

ryebread       9.2     4930    12.4      439     1.1       82

poundcake     24.8     1829     8.0      130      .4       31

crackers      15.1     3004    12.5      288      .5       50

milk          11.0     8867     6.1      310    10.5       18

evapmild       6.7     6035     8.4      422    15.1        9

butter        20.8     1473    10.8        9      .2        3

margarine     16.1     2817    20.6       17      .6        6

eggs          32.6     1857     2.9      238     1.0       52

cheese        24.2     1874     7.4      448    16.4       19

cream         14.1     1689     3.5       49     1.7        3

peanutbutter  17.9     2534    15.7      661     1.0       48

mayonnaise    16.7     1198     8.6       18      .2        8

crisco        20.3     2234    20.1        0      .0        0

lard           9.8     4628    41.7        0      .0        0

sirloinsteak  39.6     1145     2.9      166      .1       34

roundsteak    36.4     1246     2.2      214      .1       32

ribroast      29.2     1553     3.4      213      .1       33

chuckroast    22.6     2007     3.6      309      .2       46

plate         14.6     3107     8.5      404      .2       62

liver         26.8     1692     2.2      333      .2      139

lambleg       27.6     1643     3.1      245      .1       20

lambchops     36.6     1239     3.3      140      .1       15

porkchops     30.7     1477     3.5      196      .2       80

porkroast     24.2     1874     4.4      249      .3       37

bacon         25.6     1772    10.4      152      .2       23

ham           27.4     1655     6.7      212      .2       31

saltpork      16.0     2835    18.8      164      .1       26

chicken       30.3     1497     1.8      184      .1       30

veal          42.3     1072     1.7      156      .1       24

salmon        13.0     3489     5.8      705     6.8       45

apples         4.4     9072     5.8       27      .5       36

bananas        6.1     4982     4.9       60      .4       30

lemons        26.0     2380     1.0       21      .5       14

oranges       30.9     4439     2.2       40     1.1       18

greenbeans     7.1     5750     2.4      138     3.7       80

cabbage        3.7     8949     2.6      125     4.0       36

carrots        4.7     6080     2.7       73     2.8       43

celery         7.3     3915      .9       51     3.0       23

lettuce        8.2     2247      .4       27     1.1       22

onions         3.6    11844     5.8      166     3.8       59

potatoes      34.0    16810    14.3      336     1.8      118

spinach        8.1     4592     1.1      106      .0      138

sweetpotato    5.1     7649     9.6      138     2.7       54

peaches       16.8     4894     3.7       20      .4       10

pears         20.4     4030     3.0        8      .3        8

pineapple     21.3     3993     2.4       16      .4        8

asparagus     27.7     1945      .4       33      .3       12

cannedgrbn    10.0     5386     1.0       54     2.0       65

porkbeans      7.1     6389     7.5      364     4.0      134

corn          10.4     5452     5.2      136      .2       16

peas          13.8     4109     2.3      136      .6       45

tomatoes       8.6     6263     1.3       63      .7       38

tomatosoup     7.6     3917     1.6       71      .6       43

driedpeach    15.7     2889     8.5       87     1.7      173

prunes         9.0     4284    12.8       99     2.5      154

raisins        9.4     4524    13.5      104     2.5      136

driedpeas      7.9     5742    20.0     1367     4.2      345

limabeans      8.9     5097    17.4     1055     3.7      459

navybeans      5.9     7688    26.9     1691    11.4      792

coffee        22.4     2025      .0        0      .0        0

tea           17.4      652      .0        0      .0        0

cocoa          8.6     2637     8.7      237     3.0       72

chocolate     16.2     1400     8.0       77     1.3       39

sugar         51.7     8773    34.9        0      .0        0

cornsirup     13.7     4996    14.7        0      .5       74

molasses      13.6     3752     9.0        0    10.3      244

stawberry     20.5     2213     6.4       11      .4        7

:           vitaminA thiamine riboflavin  niacin  ascorbicAcid :=

#          (1000 IU)  (mg.)      (mg.)     (mg.)     (mg.)

flour           .0    55.4       33.3       441         0

macaroni        .0     3.2        1.9        68         0

cereal          .0    14.4        8.8       114         0

cornflakes      .0    13.5        2.3        68         0

cornmeal      30.9    17.4        7.9       106         0

grits           .0    10.6        1.6       110         0

rice            .0     2.0        4.8        60         0

oats            .0    37.1        8.9        64         0

whitebread      .0    13.8        8.5       126         0

wheatbread      .0    13.9        6.4       160         0

ryebread        .0     9.9        3.0        66         0

poundcake     18.9     2.8        3.0        17         0

crackers        .0      .0         .0         0         0

milk          16.8     4.0       16.0         7       177

evapmild      26.0     3.0       23.5        11        60

butter        44.2      .0         .2         2         0

margarine     55.8      .2         .0         0         0

eggs          18.6     2.8        6.5         1         0

cheese        28.1      .8       10.3         4         0

cream         16.9      .6        2.5         0        17

peanutbutter    .0     9.6        8.1       471         0

mayonnaise     2.7      .4         .5         0         0

crisco          .0      .0         .0         0         0

lard            .2      .0         .5         5         0

sirloinsteak    .2     2.1        2.9        69         0

roundsteak      .4     2.5        2.4        87         0

ribroast        .0      .0        2.0         0         0

chuckroast      .4     1.0        4.0       120         0

plate           .0      .9         .0         0         0

liver        169.2     6.4       50.8       316       525

lambleg         .0     2.8        3.0        86         0

lambchops       .0     1.7        2.7        54         0

porkchops       .0    17.4        2.7        60         0

porkroast       .0    18.2        3.6        79         0

bacon           .0     1.8        1.8        71         0

ham             .0     9.9        3.3        50         0

saltpork        .0     1.4        1.8         0         0

chicken         .1      .9        1.8        68        46

veal            .0     1.4        2.4        57         0

salmon         3.5     1.0        4.9       209         0

apples         7.3     3.6        2.7         5       544

bananas       17.4     2.5        3.5        28       498

lemons          .0      .5         .0         4       952

oranges       11.1     3.6        1.3        10      1993

greenbeans    69.0     4.3        5.8        37       862

cabbage        7.2     9.0        4.5        26      5369

carrots      188.5     6.1        4.3        89       608

celery          .9     1.4        1.4         9       313

lettuce      112.4     1.8        3.4        11       449

onions        16.6     4.7        5.9        21      1184

potatoes       6.7    29.4        7.1       198      2522

spinach      918.4     5.7       13.8        33      2755

sweetpotato  290.7     8.4        5.4        83      1912

peaches       21.5      .5        1.0        31       196

pears           .8      .8         .8         5        81

pineapple      2.0     2.8         .8         7       399

asparagus     16.3     1.4        2.1        17       272

cannedgrbn    53.9     1.6        4.3        32       431

porkbeans      3.5     8.3        7.7        56         0

corn          12.0     1.6        2.7        42       218

peas          34.9     4.9        2.5        37       370

tomatoes      53.2     3.4        2.5        36      1253

tomatosoup    57.9     3.5        2.4        67       862

driedpeach    86.8     1.2        4.3        55        57

prunes        85.7     3.9        4.3        65       257

raisins        4.5     6.3        1.4        24       136

driedpeas      2.9    28.7       18.4       162         0

limabeans      5.1    26.9       38.2        93         0

navybeans       .0    38.4       24.6       217         0

coffee          .0     4.0        5.1        50         0

tea             .0      .0        2.3        42         0

cocoa           .0     2.0       11.9        40         0

chocolate       .0      .9        3.4        14         0

sugar           .0      .0         .0         0         0

cornsirup       .0      .0         .0         5         0

molasses        .0     1.9        7.5       146         0

stawberry       .2      .2         .4         3         0

;

param allowance :=

calories       3

protein       70

calcium         .8

iron          12

vitaminA       5

thiamine       1.8

riboflavin     2.7

niacin        18

ascorbicAcid  75

;

end;