Abstract

The “Diet Problem” originated in the 1940s when researchers were tasked with determining the lowest-cost subsistence diet for a U.S. soldier. Originally, the task was accomplished through basic heuristics, but later the problem was solved using the simplex algorithm-the basis for modern linear programming. Enhancements to computing technology enabled further constraint consideration, including environmental and palatability constraints. In late 2019, the COVID-19 pandemic began to sweep the planet, resulting in the unavailability of staple food products in the United States, coupled with stay-at-home requirements. This study aimed to add scarcity constraints (food availability and time) to the Diet Problem to demonstrate that, even during a pandemic, healthy eating can be maintained, visits to the supermarket can be limited to reduce exposure, and this can be done relatively inexpensively. A diversified meal plan for a hypothetical family of four was identified at a total monthly cost of $641.51. This study not only demonstrates that healthy eating can be cost-effectively maintained by consumers during a global pandemic but also that shopping trips can be limited to reduce exposure and maintain social distance. Additionally, linear programming-not normally considered by academic researchers-is showcased as a methodology that can be used by other researchers to solve novel problems.

1. Introduction

In academic business publishing, similar to other fields, nearly all hypotheses are empirically tested using traditional statistical methods ¹. Over the years, many authors in the business literature-especially in the field of operations research-have used linear programming as an alternative to traditional statistical methods ^{2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

Linear optimization, also called “linear programming,” is a mathematical method for maximizing or minimizing a linear objective function given a system of linear constraints. An objective function defines the quantity to be optimized, with the purpose of determining the values of the variables that maximize or minimize the objective function without violating the constraints. This is done by first determining all the feasible solutions given the constraints (called the “feasibility region”) and then finding the optimal solution to the objective function ⁴. Often, as the number of constraints is increased no solution can be found, in which case constraints can be eased systematically until a “best” solution is realized. In 1947, based upon the “input-output” methodologies of Wassily Leontief, George Dantzig identified the simplex algorithm, which is the basis for modern linear programming ^{12, 13}. The simplex algorithm seeks to identify the optimal solution by systematically assessing each subsequent feasible solution along the edge of the feasibility region ¹⁴.

About a decade before Dantzig’s development of the simplex algorithm, Stigler was tasked to formulate a subsistence diet for the U.S. military. The goal was to minimize costs while delivering the Recommended Daily Allowances (RDAs) for a soldier ¹⁵. This became known as the “Diet Problem.” Stigler’s initial findings were that, for $39.93 per annum ($751.81 in 2019 dollars), the U.S. military could feed a soldier while meeting the then-current nutritional standards. This annual subsistence diet consisted of five components: (1) 370 pounds of wheat flour, (2) 57 cans of evaporated milk, (3) 111 pounds of cabbage, (4) 23 pounds of spinach, and (5) 285 pounds of navy beans ¹⁵. Stigler used a heuristic method to solve the Diet Problem. When this analysis was repeated using the simplex algorithm, Stigler’s finding was off by only 0.60% ¹⁸. Of course, this solution meant that a soldier would eat the same “meal” three times a day, every day. Thus, the Diet Problem was solved mathematically, but the solution validity was questionable. As Stigler himself stated, “No one recommends these diets for anyone, let alone everyone” ¹⁵. Justifiably criticized as the “human dog biscuit” ¹⁶, Stigler’s Diet Problem solution propelled Stigler’s career, which culminated with him winning the Nobel Prize for Economics in 1982.

The Diet Problem has been revisited many times in the academic literature. The early reformulations, which were conducted when computing power was more limited than it is today, focused on modified constraints, such as updated RDA guidelines and food availability/pricing ¹⁷. In some cases, different population subsets were assessed, such as age groups and genders ¹⁸. As early as 1941-even before Stigler-Norwegian Nobel laureate economist Ragnar Frisch argued for the requirement for food to be palatable as well as nutritional when determining optimal human diets ¹⁹. By 1959, studies began looking at food that, unlike Stigler’s solution, was consumed by the general public ²⁰. In 1970, Eckstein proposed that the term “Diet Problem” be used in reference to animals only, as palatability and variability were not a concern for animals. Eckstein noted that, when referencing humans, “Menu Problem” is a better descriptor ²¹.

As computing power increases, academic researchers can perform more complex linear programming calculations. This has led to not only adding meal palatability as a constraint ²⁰ but also adding environmental sustainability ²².

According to Van Dooren, since 2000 there have been 52 academic papers published on the Diet Problem ²³. All 24 of the papers published between 2000 and 2009 used the traditional Diet Problem formulation of cost minimization constrained by nutritional requirements. Beginning in 2009, however, additional constraints began to emerge. For the period between 2009 and 2018, of the 28 publications focused on the Diet Problem, 10 utilized the traditional formulation, 12 added only environmental constraints, four added only palatability constraints, and two added both environmental and palatability constraints ^{24, 25}.

By mid-March 2020, the COVID-19 pandemic had caused a scarcity of numerous food products in U.S. supermarkets. Many normally-available products were missing from store shelves, including fresh bread, chicken, and meat (except frozen bulk ground beef), most fresh vegetables, nearly all canned vegetables and soups, and most “fast meals” (e.g., ramen noodles). By early April 2020, shelter-in-place orders had gone into effect in most states, inhibiting visits to supermarkets and trips to get “take-out” food from restaurants. Nearly all restaurants were closed for sit-down dining by early April. At the time of this writing, more than 36 million Americans had filed unemployment claims (22% of the workforce), with many more questioning their future job status and numerous others facing a reduced work schedule ²⁶. Driven by food unavailability, shelter-in-place orders, and constrained budgets, every U.S. family has been forced to re-evaluate its meal planning. The author viewed this as an opportunity to revisit the Diet Problem.

The traditional Diet Problem is a linear minimization problem subject to nutritional constraints. Over the last 20 years, increased computing power has enabled researchers to handle additional constraints. The goal of the author of this study is to demonstrate how to feed a family effectively during a pandemic.

This study minimizes family food costs subject to nutritional constraints, food availability, palatability of food combinations, and meal variation, and also restricts food shopping to one trip per month.

2. Methodology and Analysis

As stated, the goal of this study is to use linear programming to determine the most economical way to feed a family effectively during a pandemic. The sub-goals are to (1) minimize cash outlays for food; (2) minimize potentially dangerous visits to the supermarket during a pandemic, specifically liming shopping trips to one shopping event per month; (3) meet RDAs for a family as a whole and for each family member individually; (4) include only menu items that are generally available during the COVID-19 scarcity period; (5) develop food menus for individual meals (breakfast, lunch, dinner, and one snack every day); and (6) provide a diversity of meals, specifically meals that vary by day (i.e., the family does not eat the same breakfast, lunch, or dinner meal every day).

This formulation of the Diet Problem is examined in three scenarios, with each scenario adding additional constraints. Following Fletcher and colleagues ²⁷, in the case in which not all constraints can be met, shadow costs are utilized to determine the best suboptimal solution.

The study assesses three scenarios and then systematically constructs a final solution. Discussed in more detail below, Scenario 1 is similar to Stigler’s approach; it uses the same menu for every meal every day, but it is based upon current RDAs and food generally available during the pandemic. This is referred to here as the “Human Dog Biscuit Scenario.” Scenario 2 adds the constraint of requiring the three traditional meals normally consumed in the United States (i.e., breakfast, lunch, dinner) together with foods that normally are eaten for those meals, but it still allows the unrealistic situation of consuming the same menu for each meal every day. This scenario is referred to here as the “3 Dog Biscuit Scenario.” The final scenario, Scenario 3, adds a meal-diversity constraint, requiring at least three different breakfasts, three different lunches, and three different dinners per week. This is referred to here as the “Realistic Scenario.”

Data on food availability during the pandemic were gathered manually by visiting three supermarkets in the Denver, Colorado, metropolitan area on two different dates during the COVID-19 pandemic: Safeway, King Soopers, and a Target Superstore. Each store had significant systematic and relatively consistent inventory shortages. One trip to each store was made on a weekday, and one trip to each store was made on a weekend during the week of March 16, 2020. Only foods that were identified on all six supermarket visits were used in the study. “Exotic” foods were excluded and, where similar items were available, the least-expensive options were selected unless cheaper options were considerably less nutritious. All information was captured via cell phone photography for further analysis. Specific food data were saved via barcode scanning using an application called “Carb Manager” (version 6.3.5, Wombat Apps LLC). In the case where data were incomplete, the missing information was sourced from the specific food supplier or, in the case of commodities (e.g., fresh salmon), from the website nutritiondata.self.com. Table 1 lists the foods that were available in sufficient quantities at all six visits to the grocery stores.

The RDA data were sourced from Appendix F of the U.S. Food and Drug Administration’s publication, A Food Labeling Guide: Guidance for Industry ²⁸. However, not all of the RDAs and associated values must be published on the “Nutrition Facts” labelling mandated for all U.S. food items ²⁸. Because this information is not readily available to the consumer, only those RDAs required by labelling guidelines are used as constraints in this consumer-oriented study. Table 2 provides a list of the RDAs that are mandated by labelling requirements in the United States. The values are based upon a 2,000-calorie per day diet.

The linear optimization model used in the present analyses is specified as follows.

(1)

In this set of equations, X is a function of the total cost of meal components, and in some problem formulations its units are required to be integers. A is a matrix containing the units of a nutrient per serving of a meal component, b is the vector of RDA lower bounds, and c is the vector of RDA upper bounds. D is a matrix containing food-meal combinations (e.g., bacon-breakfast), and e is the vector of meal constraints (e.g., the minimum number of different meals per week).

Linear optimization was performed using Excel 365 (version 2003.12624.20320) with the Solver Plugin. The simplex algorithm ¹² was used, except in the case of non-linear constraints, in which case the Generalized Reduced Gradient non-linear algorithm was used instead ²⁹.

As discussed, the “Human Dog Biscuit Scenario” is similar to Stigler’s approach-the same menu for every meal every day-but it is based upon current RDAs and foods generally available during the pandemic. There are three sub-scenarios, with constraints added in turn. In Scenario 1a, partial servings are allowed, meaning that the suggested “serving size” on the FDA-mandated product labels is not required to be followed. In Scenario 1b, partial servings are not allowed, so an integer constraint is imposed. In Scenario 1c, partial servings are not allowed, and no more than one serving of any food is allowed per meal. All RDA constraints shown in Table 2 are included in the analysis, as is each of the 51 foods listed in Table 1.

Scenario 2 has the constraints of the current RDAs and food generally available during the pandemic and adds a constraint requiring the three daily meals normally consumed in the United States (i.e., breakfast, lunch, and dinner) as well as an additional constraint requiring that only foods that are traditionally consumed in those meals are available for those meals. To determine which foods traditionally were consumed with each meal, the author followed Leung et al., who determined food-combination palatability based upon modern recipes ³⁰. Each of the 51 foods is characterized as breakfast food, lunch food, dinner food, snack food, or drink/fluid. Foods can be in more than one category, but only foods that are characterized for a specific meal are included in the scenario for that specific meal type (i.e., bacon is only characterized as a breakfast food, so it is not included in the lunch or dinner sub-scenarios). This categorization results in 19 breakfast foods, 24 lunch foods, 19 dinner foods, 14 snack foods, and three drinks. The food-meal type categories determined for this study are shown in Table 3. Additionally, this scenario still allows the unrealistic situation of consuming the same menu for each meal every day.

Scenario 2 has several sub-scenarios for each meal type. The breakfast scenarios are described here, with the lunch and dinner scenarios being identical except for the included foods, as described in Table 3. Similar to Scenario 1, in Scenario Breakfast 2a (B2a) partial servings of the meal component are allowed. In Scenario Breakfast 2b (B2b), however, partial servings are not allowed. In addition to the integer constraint imposed in B2b, Scenario Breakfast 2c (B2c) requires that no more than one serving of any food is allowed per meal. Following Parlesak and colleagues’ work on “food baskets” ³¹, and unlike Scenario 1, Scenario Breakfast 2d (B2d) adds to the B2c constraints one that this study calls “optimized meals.” Optimized meals require that certain foods be consumed together (e.g., pancakes require syrup; dry cereal requires milk). The lunch scenarios are denoted as Scenarios L2a through L2d, and the dinner scenarios are Scenarios D2a through D2d.

For Scenario 3-the most realistic of all the scenarios in this analysis-the author followed Petot et al. and determined menus for seven different commonly eaten meals for each meal type (breakfast, lunch, and dinner), based upon the 51 foods available, and identified 11 snacks and three drinks ³². The breakdown is shown in Table 4.

Scenario 3 includes Scenario 2 constraints of individual meals (breakfast, lunch, and dinner) and adds a snack each day. Additionally, Scenario 3c includes a meal-diversity constraint that requires at least three different breakfasts, three different lunches, and three different dinners per week. Similar to the other scenarios, there are several sub-scenarios in Scenario 3. Scenario 3a-in addition to the RDA constraints and pandemic-driven meal-availability constraints-requires three meals of any type, a snack, and three drinks per day for 28 days, but partial meals are allowed. Scenario 3b is very similar to Scenario 3a, except partial meals are not allowed. Finally, Scenario 3c includes all Scenario 3b constraints but requires meal diversity, meaning that at least three different breakfasts, three different lunches, and three different dinners must be consumed per week.

Table 5 provides a summary of all constraints in addition to the RDA and food-availability constraints for all 10 scenarios.

3. Results

For the purpose of this study, a theoretical family of four with the following attributes was considered: (1) a moderately active man, age 41, consuming the recommended 2,600 calories per day; (2) an active woman, age 35, consuming the recommended 2,200 calories per day; (3) a sedentary male child, age 12, consuming the recommended 1,800 calories per day; and (4) a moderately active female child, age 6, consuming 1,400 calories per day. The female parent is not pregnant and is not planning to become pregnant in the foreseeable future. No family members identified significant health issues, and no family members have any allergies or self-imposed eating restrictions (e.g., no family member is a vegetarian). This family needs to consume the nutrients associated with 8,000 calories per day total. The goal was to feed the family-maintaining all RDAs (as defined)-for one month (28 days) with only one visit to the supermarket (food items either must last 28 days or can be frozen without significant impairment in quality).

As discussed, Scenario 1 is the “Human Dog Biscuit Scenario”; there is only one menu of food for each day. The results of Scenario 1 are shown in Table 6.

For all three sub-scenarios, the constraints are met, except for the calorie constraint for 1b (Table 6, Panel B) and 1c (Table 6, Panel C), which are within 2.0% of holding. As constraints are imposed, costs increase-from an average of $2.55 per family member per day for Scenario 1a to an average of $3.00 per family member per day for Scenario 2c. Scenario 1c begins to become palatable; but, as noted, it is unlikely that any family would choose this diet for more than one day, much less for an entire month. This scenario, however, can serve as the “base case” for comparison with the remaining scenarios.

As mentioned, Scenario 2 is the “3 Dog Biscuit Scenario”; namely, a distinct breakfast, a distinct lunch, and a distinct dinner but the same breakfast, lunch, and dinner every day. Because each meal is a unique subproblem of the scenario, each is discussed in turn below. Additionally, the three meals together are based upon a 2,000-calorie diet, with 40% of the calories allocated to dinner and 30% each to breakfast and lunch.

All Scenario 2 breakfast foods (Scenarios 2Ba through 2Bd) are shown in Table 7.

As shown in Table 7, the breakfast meal becomes much more expensive as constraints are added. There is a 215.2% increase from Scenario 2Ba to Scenario 2Bd (an average of $1.05 to $3.31 per family member per day), driven predominately by palatability constraints, even given that all RDA constraints are not met in Scenarios 2Bc and 2Bd, with the total fat constraint being relaxed in Scenario 2Bc (106.2%), and with the total carbohydrate constraint being relaxed in Scenario 2Bd (120.5%). Without relaxing constraints, there are no solutions to the problems identified in these scenarios. The solutions shown are not the only possible solutions; however, they were the solutions that allowed the minimum deviation from a single constraint to solve the problem and minimize that deviation in percentage terms. As discussed by Maillot and colleagues, very few Americans meet 100% of the RDAs on any day, much less every day ³³. The author, therefore, deemed these slight deviations from a single RDA to be acceptable. Scenario 2Bd (Panel D) is a very palatable breakfast menu, as determined by the meal being available in nearly every American breakfast restaurant ³⁴.

All Scenario 2 lunch menus (Scenarios 2La through 2Ld) are shown in Table 8.

As in Scenario 2B, Scenario 2L exhibits increasing costs as constraints are added. Note, however, that Scenario 2Lc costs decrease from those of Scenario 2Lb because not all constraints hold. Specifically, in Scenario 2Lc (Table 8, Panel C), total fat exceeds the RDA by 15.4% and sodium exceeds the RDA by 77.1%. Given these facts-especially the sodium amount-the author determined that the optimal constraint to be relaxed was not a nutrient constraint but rather the constraint that limited meals to single-component servings. This resulted in the solution to Scenario 2Ld (Table 8, Panel D) being a double serving of soy milk with lunch. The author deemed this to be palatable because it results in a 16-ounce serving of soy milk, which is 69.6% of the average amount of a drink consumed per meal based upon a serving size study by Bryant and Dundes ³⁵.

All Scenario 2 dinner menus (Scenarios 2Da through 2Dd) are shown in Table 9 below.

As expected, the cost increases as each constraint is added in Scenario 2D, concluding with a total average cost of $2.77 per family member per day for the optimized meal (Table 9, Panel D). The calorie constraint is within 6.3% of the goal, which is a function of integer-serving requirements, but the sodium RDA is exceeded by 17.9%. As in Scenarios 2Bd and 2Ld, no solution can be found where all constraints hold.

When considering the final sub-scenario of each meal type in Scenario 2 (Panel D of Table 7, Table 8, and Table 9), the total average cost per family member per day is $8.82, even though not all constraints hold in every case. This is substantially more expensive than Scenario 1, where the most palatable option, Scenario 1C (Table 6, Panel C), costs an average of $3.00 per family member per day. The cost of meal diversity, in this case, a breakfast of breakfast-specific foods, a lunch of lunch-specific foods, and a dinner of dinner-specific foods versus a single menu for every meal every day, comes at a significant cost increase, specifically a 194.0% premium.

As discussed, Scenario 3 is the “realistic scenario,” as a series of breakfast meals, a series of lunch meals, and a series of dinner meals were determined based upon available foods and common tastes. Scenario 3a allows partial meals, but Scenario 3b does not. Scenario 3c does not allow partial meals and requires meal diversity (i.e., at least three different breakfasts, three different lunches, and three different dinners per week). The results of Scenario 3 are shown in Table 10.

As expected, the addition of constraints increases costs from Scenario 3a to Scenario 3b to Scenario 3c (Table 10, Panels A, B, and C, respectively). None of these scenarios can be solved without relaxing at least one constraint, and Scenario 3c requires the relaxation of several constraints, given its complexity.

In addition to the relaxed constraints shown explicitly in Table 10, there is another significant relaxation of the RDA constraint for all sub-scenarios in Scenario 3: all RDAs are an average of a 28-day month. In all prior scenarios, the RDAs are a true daily average. This is a significant relaxation of constraints, but the author deemed it to be realistic for the meal planning of an average U.S. family. For this reason, the overall cost of Scenario 3c-the most expensive sub-scenario in Scenario 3-is an average of $5.33 per family member per day (Table 10, Panel C), considerably less than the most expensive sub-scenarios in Scenario 2 (at $8.82) (see Table 7, Panel D; Table 8; and Table 9).

Because the number of meals by type per week is a non-linear constraint, a different optimization method was required to solve Scenario 3c (Table 10, Panel C)-the Generalized Reduced Gradient non-linear algorithm (GRG Method) was employed ²⁹.

The author regards Scenario 3c (Table 10, Panel C) as the most realistic scenario for actual family meal planning, given that all of the other scenarios in this study are not practical ways for a family to eat over an extended period, such as a month. Because of the relaxation of multiple constraints, however, the cost per day of this scenario for a 2,000-calorie diet is less than that of Scenario 2, but it is much greater than all sub-scenarios in Scenario 1, as shown in Figure 1.

Scenario 1 increases in cost with each additional constraint. Scenario 2 is very expensive because each meal is optimized and very few constraints are violated (i.e., more diversity than Scenario 1). Scenario 3 is less expensive than Scenario 2 because six RDAs are not met (although the delta is minimized in each case), but the more impactful constraint is that the RDA levels are optimized on average for the month, not for each day.

As discussed, the goal of this study is to demonstrate that a family can be effectively fed a palatable and diversified diet during a pandemic while minimizing costs and trips to the supermarket and meeting minimum RDAs to the extent possible. Because our foods are bought per container and in bulk, there will be some “leftovers” at the end of the 28-day month. Using the results of Scenario 3c-the most realistic scenario for actual family meal planning-the hypothetical family of four would make one grocery store trip at the beginning of the month and would purchase all of the items listed in Table 11, at a total cost of $631.52.

After a full month of meals, there are some leftovers for our hypothetical family of four, specifically because the constraints of Scenario 3c were to require full servings, but the food is purchased per unit or per container. The total value of the leftovers is $34.56.

4. Conclusions

The Stigler Diet Problem was revisited under the constraints of the current-day COVID-19 pandemic. The author identified 51 readily available meal ingredients that could be stored for a minimum of a month (frozen or otherwise). Several scenarios were analyzed, with the goals of minimizing costs, meeting minimum RDAs, and maximizing edibility/diversity. An additional goal was requiring only one shopping event per month, thus minimizing exposure to COVID-19. An acceptable and diversified one-month meal plan that minimized costs and minimized the relaxation of average monthly minimum RDAs was identified for a hypothetical family of four. The total monthly cost of this meal plan is $631.52. Certain RDAs, however, were not met on average over the course of the month due to the complexity of the imposed constraints. Specifically, the family would exceed total fat allowances by about 18.4%, total saturated fat RDA by 11.6%, and the sodium RDA by 33.3%; however, most families in the United States regularly exceed many of the maximum RDAs ³³. Certain minimum RDAs are not met by this proposed diet, specifically potassium (84.6% of the RDA) and Vitamin A (62.4% of the RDA). These nutrients are readily available as dietary supplements at U.S. supermarkets. It costs an estimated additional $0.36 per day ($9.99 per month) for supplements for the family to meet the RDAs of these nutrients, bringing the final cost to $641.51.

This study serves dual purposes. First, it highlights linear optimization, a method not normally considered by business researchers. More importantly, the results here can be used as a blueprint to demonstrate to families that healthy menus can be purchased very inexpensively from supermarkets during pandemic-related scarcities, and visits to the supermarket can also be limited to one per month to reduce dangerous exposure. Although the available foods in this study were identified in the Denver, Colorado, metropolitan area at the height of the pandemic, it is likely that the global supply chains of the major grocery store chains assessed in this study would be similar across the country, albeit not without regional or super-regional differences. Additionally, it is unlikely that a family would follow this exact blueprint for pandemic meal planning. Even in the case where the identified foods are not available in different areas of the country-or if family taste differences existed-the U.S. food labeling guidelines are such that it would not be time-consuming or challenging to substitute foods in the grocery list in Table 11 with other foods with similar nutrient values.

References