Optimizing Meal Planning (Part One in a series)

The Problem to Solve

I've been developing a process for optimizing meals in my household. I want to be able to have an inventory of ingredients and other food stuffs and be able to figure out a meal to make. These are the different problems I want to be able to solve:
  • Given what's in the house, what meals can we make which meet our nutritional needs and maximize the number of meals we can make?
  • What is the meal that costs the least and meets our minimum nutritional needs?
  • Plan a grocery shopping list by figuring out meals for breakfast, lunch, and dinner for a 15 day period that meet prep time, meal diversity, and nutrition constraints.
  • Also, phase in caloric constraints over time to prevent weight gain.
If you're familiar with Linear Programming you may recognize this as a variant of "The Diet Problem". You can read more about the full diet problem here: http://www.neos-guide.org/content/diet-problem. The most important take away is that this kind of problem can be solved using optimization methods such as Linear Programming. 

As a proof of concept, I've started laying out a small toy version of this problem to see if it holds water. If it does, I plan to continue to develop a manual solution and then, if that works, I might automate a general solution.

Formulating the Model

Let's first solve the problem of maximizing the number of meals we can make given what we have on hand. In order to solve this problem with Linear Programming we need to formulate an objective function which we want to maximize. I've laid out a few common meals from my household. For this problem, the meals will be what we call the decision variables. These are the inputs into the model that we change in order to maximize the objective function. The reason for choosing that the decision variables be the actual meals and not the ingredients (in case you are wondering) is that the meals are what need to be planned. The ingredients give us information about the nutrition for use by our constraints but they don't determine the meals on their own.

Let's start by figuring out an objective function for this problem. First, I defined six meals to act as decision variables. Those are:

For this first simple proof of concept, our objective function is pretty simple though the constraints of the model will get a bit lengthy.

Since we want to just maximize the number of meals, our objective function is simply the sum of the number of meals:

Great! Next we need to define our list of ingredients. Notice that the amount of each ingredient is a function of the meals each is included in. Here are the definitions of the ingredients:

And then this is how each of the ingredients relates to the individual meals along with our constraints about how much we have on hand.

Solving the model

We still haven't entered in the nutrition information! That's ok for now. This is just the proof of concept. Let's stop here and try to solve the model. You may want to use Google Docs or Excel; I'm going to choose Excel.

At another point I will get into how exactly to solve this model in Excel. For now, I want to show the power of this approach so I will keep things brief by just giving you the answer and providing the Excel spreadsheet.

According to Excel, the maximum number of meals I can create given the above constraints on my inventory is 10.75 meals. Specifically:
  • 0.75 servings of spaghetti
  • 0 veggie pepperoni pizza
  • 1 serving of veggie chili dogs (two hot dogs)
  • 3 servings of chili
  • 2 servings of eggs and toast
  • 4 servings of peanut butter and jelly sandwiches
Not only do we know exactly what meals we can make, but we also are left knowing how much of each ingredient we will have left over:
  • Spaghetti noodles: 137.5 grams
  • Boca crumbles: 0.625 lbs
  • Marinara sauce: 0 cups
  • Broccoli: 37.5 grams
  • Pizza dough: (still) 0
  • Mozzarella cheese: 3.5 cups
  • Veggie pepperoni: 11 pepperonis
  • Veggie chili: 1.5 cans
  • Hot dog buns: 1 bun
  • Veggie hot dogs: 0 hot dogs
  • Grated cheddar cheese: 0 cups
  • Eggs: 0 eggs
  • Butter: 0.08 cups
  • Bread: 0 slices
  • Peanut butter: 1 cup
  • Jelly: 1 cup
For a second I thought having 1.5 cans of chili left over was a bug. I realized though that according to my recipe I can't make veggie chili without cheddar cheese. Since I have none of that left, I can't make chili!

Now if I also had listed the amount of money each ingredient costs I could also list how much money I'm paying per meal. As I said earlier, if I had nutrition info, I could put extra constraints around nutrition. If I wanted to ensure half my meals aren't PB&J I could add a constraint for that as well. The list goes on.

Once I entered the data, the model takes less than a second to run (so far). We'll see how the performance fares as I increase the complexity of it.

In the next blog post, I will continue this analysis but will start to include more realistic estimates for ingredients including calories and nutrition so that we can start to solve some more interesting problems.