When George Dantzig Optimized His Personal Diet Problem

The “diet problem” has a particular meaning in academic literature. We know nutritional ingredients and calorie counts in various foods. We know the price of these foods to the consumer. We know what combination of vitamins, minerals, and calories are needed to maintain health. With this information, what is the least-expensive diet sufficient for human health?

A number of readers will recognize this as a classic problem in linear programming, which allows one to optimize (meaning to find a maximum or minimum value) in the presence of constraints. But I should emphasize that the “diet problem” has very real practical consequences. The original basis for the creation of an official US poverty line, back in the 1960s, was based on the work of Mollie Orshansky, who had worked for some years collecting data about family budgets and costs of preparing low- and moderate-cost meals. Orshansky suggested that since the average family in the early 1960s spent one-third of its income on food, then a plausible poverty line was the cost of a low-cost but nutritionally adequate diet multiplied by three. In this way, the US poverty line was designed to vary by the number of people in a household. In looking at malnourishment and standards of living around the world, the question of what would be included in the minimum-cost but adequate human diet is of great practical relevance.

George Dantzig (1914-2005) is sometimes called the “father of linear programming” for his development in 1947 of “the simplex algorithm” to solve these problems. In a 1990 essay, “The Diet Problem,” Dantzig tells the story of coming to grips with the diet problem intellectually– and also what happened when he tried to apply it to his own diet (Interfaces: The Practice of Mathematical Programming, July-August 1990, 20: 4, pp. 43-47).

As Dantzig tells the story, he had been working for the Air Force during World War II. The question of how to optimize subject to constraints had potentially very wide wide applicability to thinking about planning, operations, and design tradeoffs. Dantzig had a theoretical answer by about 1946 or 1947, but he was looking for a real-world example on which he could test it: “Marvin Hoffenberg suggested we test it on Jerry Cornfield’s diet problem. Jerry said that he had worked on the problem several years earlier for the Army who wanted a low cost diet that would meet the nutritional needs of a GI soldier.” Cornfield had the data, but couldn’t figure how to solve for the low-cost diet.

Dantzig began asking around for who else had worked on the problem, and learned that George Stigler has published “The Cost of Subsistence” in 1945 (Journal of Farm Economics, May 1945, 27:2, pp. 303-314). Stigler started with a list of nine necessary ingredients for a healthy diet from a 1943 National Research Council report:

Stigler also had data on the retail prices of 77 foods from US Bureau of Labor Statistics. Thus, he set out to calculate the minimum cost of buying a nutritionally adequate diet based on these 77 foods.

Stigler was quite open about the shortcomings of his approach. On the issue of nutritional needs, he wrote: “In addition to calories, the body requires about thirteen minerals (some in very minute quantities), and perhaps half as many vitamins. Protein contains two dozen amino acids, of which almost half are necessary to human beings. The precise determination of our needs for these–and no doubt other yet undiscovered–nutrients lies far in the future. Nevertheless standards of dietary adequacy have been established, perhaps prematurely and certainly very tentatively.” Stigler’s list of 77 foods was limited. As he points out, “The BLS list is a short one, and it excludes almost all fresh fruits, nuts, many cheap vegetables rich in nutrients, and fresh fish. It is beyond question that with a fuller list the minimum cost of meeting the National Research Council’s allowances could be reduced, possibly by a substantial amount.” Also, Stigler points out that “[m]any nutritive values have not been established quantitatively” and that “[m]ost foods are not even approximately homogeneous”; for example, 100 grams of a “Ontario” apple variety has four times as much ascorbic acid as 100 grams of a “Jonathan” apple.

But research on many questions often proceeds in a spirit that thinking through how to address a problem with the information at hand is a useful exercise, even with the knowledge that one is likely to want to revisit the problem later with better information. Thus, Stigler took a shot at a plausible answer: “Thereafter the procedure is experimental because there does not appear to be any direct method of finding the minimum of a linear function subject to linear conditions. By making linear combinations of various commodities it is possible to construct a composite commodity which is superior in all respects to some survivor, and by this process the list of eligible commodities can be reduced at least to nine … “

Here is Stigler’s minimum cost annual diet for August 1939 and August 1944. The cost of evaporated milk and dried navy beans rises during World War II, so they are substituted out for other items in the 1944 diet.

Stigler points out that estimates of the lowest-cost adequate diets from professional nutritionists at this time were much higher than his estimate:

These low-cost diets of the professional dieticians thus cost about two or three times as much as a minimum cost diet. Why do these conventional diets cost so much? The answer is evident from their composition. The dieticians take account of the palatability of foods, variety of diet, prestige of various foods, and other cultural facets of consumption.

As Stigler point out, the pure minimum-cost diet is an abstraction. He is careful to note that “no one recommends these diets for anyone, let alone everyone.” He also points out that for just a slightly higher cost, it is possible to add a much greater amount of variety to the diet. However, economist Stigler also argues that, as a matter of analysis, it is useful to separate the minimum-cost diet based on physical needs from the the minimum-cost that includes palatability and “cultural facets.”

In George Dantzig’s 1990 essay, he remembers the Stigler essay as “quite remarkable.” The data that Stigler had used thus became a first test for Dantzig’s proposed simplex method. Dantzig writes:

In the fall of 1947, Jack Laderman of the Mathematical Tables Project of the National Bureau of Standards undertook as a test of the newly proposed simplex method the determination of a least cost adequate diet based on Stigler’s data. It was the first “large scale” computation in the field. The system consisted of 9 equations in 77 unknowns. Jack parcelled out a different 8 or 9 columns (of the 77 columns) to each of the nine clerks who were assigned to process them. Using hand-operated desk calculators (this was in the days before computers), the nine clerks took approximately 120 man days to obtain an optimal solution of $39.69. Stigler’s heuristic solution was only off from the true annual optimal cost by 24 cents: not bad!

The clerks recorded their work for each iteration on a separate work sheet. Later, after the job was complete, Jack joined the separate sheets together to form one large sheet which we dubbed the Table Cloth. I have a letter in my files from Oskar Morgenstern (who with von Neumann wrote the famous treatise on game theory) saying he would like to come down from Princeton to Washington to view it. Eventually the table cloth disappeared, never to be seen again.

But the story doesn’t end there. In the early 1950s, Dantzig and his wife Anne moved to the RAND Corporation in California. Dantzig’s doctor told him that he needed to lose some weight. Thus, Dantzig decided that he would set up a programming problem not to have a least-cost nutritionally adequate diet, but instead to set up an under-1500 calorie, but makes-you-feel-full diet. He tells the story this way:

My doctor advised me to go on a diet to lose weight. I decided I would model my diet problem as a linear program and let the computer decide my diet. Some revisions of the earlier model, of course, would be necessary in order to give me a greater variety of foods to choose from; the calorie intake had to be reduced to under 1,500 calories per day; and the objective function had to be changed (I wasn’t interested in saving money). I said to myself: “The trouble with a diet is that one’s always hungry. What I need to do is maximize the feeling of feeling full.” After giving much thought to what the coefficients in the objective form should be, I used the weight (per unit amount) of a food minus the weight of its water content. Input data for over 500 different foods was punched into cards and fed into Rand’s IBM 701 computer. My colleague Ray Fulkerson (famous for his contributions to network flow and matroid theory) was skeptical. “You crazy or something? We solve models to obtain optimal schedules of activities for others to follow, not for ourselves.’ Nevertheless I was determined to do just that.

As I’m sure Dantzig expected, the linear programming as he had posed it to the computer did not include all the issues that mattered, and so the computer pumped out some peculiar dietary recommendations. Again, Dantzig tells the story:

One day I said to Anne, my wife, ‘Today is Der Tag, whatever the 701 says that’s what I want you to feed me each day starting with supper tonight.” Around 5:00 PM, Anne called, “Nu, it’s five and you haven’t called. What should I be cooking?” I replied that she didn’t really want to know. I then read off the amounts of foods in the optimal diet. Her reaction: “The diet is a bit weird but conceivable. Is that it?” “Not exactly,” I replied, “AND 500 gallons of vinegar.” She thought it funny and laughed.

I figured there had to be a mistake somewhere. It turned out that our data source listed vinegar as a very weak acid with water content = zero. Therefore, according to the way the model was formulated the more vinegar you drank the greater would be your feeling of feeling full. I decided that vinegar wasn’t a food.

The next day the above scene was repeated except this time I called Anne in time to prepare supper. Again the diet seemed to be plausable except for calling for the consumption of 200 bouillon cubes per day. Anne made one of the great puns of all time: “What are you trying to do, corner the bullion market?” The next day started with a test to see how many Bovril bouillon cubes I could consume for break fast. I decided to begin by mixing four in a cup of hot water. I had to spit it out: it was pure brine! I called my doctor and asked him how come the nutritional requirements didn’t show a limit on the amount of salt? “Isn’t too much salt dangerous?” He replied that it wasn’t necessary; most people had enough sense not to consume too much. I placed an upper bound of three on the number of bouillon cubes consumed per day. That was how upper bounds on variables in linear programming first began.

The next day the above scene was repeated, except this time the diet called, among other things, for two pounds of bran per day. Anne said, “If you consume that much bran, I doubt you’ll make it to the hospital. I’ll tell you what I will do (she was beginning to take charge): I’ll buy some finely milled bran and limit you to no more than a couple of cupfuls per day.” The model was revised with an upper bound put on the amount of bran. The next day the proposed menu was almost exactly the same except this time it was two pounds of blackstrap molasses which substituted for the bran; apparently their nutritional contents were quite similar.

At this point Anne got tired of the whole game. Speaking firmly so that I would know who was boss, she said, “I have been studying the various menus the computer has been generating. There are some good ideas there that I can use. I’ll put you on MY diet.” She did and I lost 22 pounds.

The deeper lesson, of course, is that computers (and now, artificial intelligence) will solve the problem as you have stated it to them. But if the problem is not stated fully–including for potential issues that just seemed so obvious that there was no need to state them–you may get ridiculous results. Even if the incorrect results are not as vivid as in Dantzig’s example, they can be deeply flawed in non-obvious ways. Thus, you need to keep judging and evaluating the feedback, perhaps by “adding upper bounds on variables.” But with such concerns duly noted, the results of such calculations can still be quite helpful in expanding one’s sense of the possible and suggesting alternatives that otherwise would not have even been considered.

The post When George Dantzig Optimized His Personal Diet Problem first appeared on Conversable Economist.