Food Optimizer

I have always been curious about how to answer questions like “what is the cheapest diet I can make out of grocery produce, subject to the constraint that I meet standard nutritional guidelines?” In the last several years a number of food substitutes / meal replacements have become popular. I’ve tried a few and enjoyed them, but was a little disappointed in how high the prices are. So, I decided to try to find my own solution!

Defining an optimization problem

After researching healthy ranges for consumption of vitamins, minerals, and macronutrients, then collecting nutritional information and prices for a few dozen foods, I constructed the following Linear Program:

• The variable $\textbf{x} \geq 0$ represents the quantity of each food to be purchased/consumed.
• The cost vector $\textbf{c}$ represents the literal cost of purchasing each food.
• Each column of the constraint matrix $\boldsymbol{A}$ represents the nutritional profile of the corresponding food.
• Each row of $\boldsymbol{A}$ corresponds to a given vitamin, mineral, or macronutrient.
• The recommended lower and upperbounds on each nutrient provide constraints $\textbf{u}$ and $\textbf{l}$ so that $\textbf{u} \geq \boldsymbol{A} \textbf{x} \geq \textbf{l}$.
• Finally, the objective function is the cost, $f(\textbf{x}) = \textbf{c}^T \textbf{x}$.

With these specifications in place, the LP to solve is

$$\min~~~~~\textbf{c}^T \textbf{x} ~~~~~~~~~~ \\ s.t.c.~~ \textbf{u} \geq \boldsymbol{A} \textbf{x} \geq \textbf{l} \\ \textbf{x} \geq 0$$

Results

Trying to solve this LP raised some interesting points.

If the LP is infeasible, that essentially means that the foods you’ve included would leave you with some nutrient deficiency. I started by using only vegan foods and quickly found that I ran into exactly this problem: the LP was infeasible because I hadn’t added enough sources of vitamin B12. To resolve this, I simply added a multivitamin pill as an optional food. (Apparently the degree to which multivitamins are useful is a subject of debate, and nutrients present in a multivitamin are not necessarily bioavailable, but these concerns are outside the scope of this post.)

Another thing I found curious was that a lot of plants ended up being good sources of nutrients that surprised me. Broccoli, for instance, has a lot of vitamin C, and more protein than I realized. Garlic has way more calcium, vitamin C, and protein than I had ever heard – in fact, some versions of the LP spit out diets that were very high in garlic, largely because garlic seems to be one of the most cost-effective sources of calcium. A number of grains/starches have more protein than I realized: oatmeal is especially high in protein (relative to other grains) as well as iron, and even potatoes have some protein.

The diet I ended up constructing was as follows (take this with a grain of salt, so to speak — I am not a medical or nutritional professional). For breakfast, oatmeal and peanut butter (no added salt or sugar). Then, for the rest of the day, a combination of potato, onion, garlic, carrot, and broccoli. Together with a multivitamin bought in bulk, and this diet is under $3.00 per day, and potentially closer to $2.00 if you buy in bulk at cheaper stores.