Algorithms (optimization problem): find collection of objects whose permutation satisfies criteria

Question

I'm putting together a personal list of recipes that I enjoy, and would like to construct an algorithm that parses this recipe database and automatically builds me a meal plan for the week.

For N number of meals per day, find permutation of recipes that comes the closest to satisfying these conditions:

• Sum of meal calories ~= my defined daily calorie limit
• Average recipe macros* (weighted by recipe calories) ~= my desired macros (i.e. (30/40/30))

(*: Macros are the ratio of carbs/protein/fats in a meal, and are usually found in a tuple form: (CC/PP/FF))

Each recipe can be assumed to be in the form:

'name': {
   'calories': a, 
   'protein': b, 
   'carbs': c, 
   'fats': d
}

In other words:

Inputs: n_meals, max_cals, (cc,pp,ff) # <- macros
Output: [recipe_1, recipe_2, ..., recipe_n]

I have no formal training in algorithms, so I'm not really sure where to start. The naive approach would be to take every permutation of recipes in the list and use the permutation which satisfies the criterion the closest.

This is definitely a multi-dimensional optimization problem but that's the depth of my knowledge. Perhaps something like a breadth-first search algorithm would be most appropriate?

Thanks all.

Answer 1

You could formulate this as an instance of integer linear programming. You use zero-or-one variables $x_{ij}$, with the intended meaning that $x_{ij}=1$ if you assign recipe $i$ on day $j$. Then your restrictions can be expressed as linear inequalities (e.g., $\sum_i x_{ij}=3$ means you eat 3 meals per day, $\sum_j x_{ij}=1$ means that you eat each recipe once). You introduce a variable $y$ that expresses how far off from the goals you're allowed to be; then the restrictions on calories and macronutrients are also linear. Finally, you feed this to an off-the-shelf ILP solver to minimize $y$.

Or, assuming you have three meals per day, you could generate all possible ways to pick a single day's menu that meets the calory requirement for that day, then exhaustively explore all possible ways to combine those daily menus into a week's worth of menus.