# Linear optimization or Constraint Satisfaction Problem with food

I was hoping someone could point me in the right direction in terms of what type of problem I am describing here so I can research it. My initial thought is that it is some form of Constraint Satisfaction Problem.

Say as an example I am working with food, and I would like to determine from a massive database of recipes which foods might sum up to equal a certain macro-nutrient profile.

For example, maybe I want to target a 410 calorie meal consisting of 30 grams of protein (4 cals per gram), 10 grams of fat (9 cals per gram) , and 50 grams of carbohydrates (4 cals per gram).

Would this be in the domain of CSP, or should I look elsewhere?

## 1 Answer

I suggest you use integer linear programming.

Suppose you have $n$ recipes. Introduce zero-or-one variables $x_1,x_2,\dots,x_n$, with the idea that $x_i=1$ represents including the $i$th recipe and $x_i=0$ represents omitting it. Now you can obtain a bunch of linear equations, one per macronutrient requirement. For instance, in your example, we get something like $c_1 x_1 + \dots + c_n x_n = 30$, where $c_i$ is the number of grams of protein contributed by the $i$th recipe. Feed this to an off-the-shelf ILP solver, and hopefully it will find a solution for you.

If you're willing to eat multiple servings of a single recipe, you can relax the constraint on each $x_i$ and require it to be an arbitrary non-negative integer ($x_i \ge 0$), instead of requiring that it be 0 or 1.

Your problem is basically a multi-dimensional subset sum problem. That's a special case of the multi-dimensional knapsack problem, which is NP-hard. There have been people who have studied algorithms for the multi-dimensional knapsack problem, but my guess is that the pragmatic solution is to start by trying an off-the-shelf ILP solver, and studying the literature only if that doesn't work.

Related: 2 Dimensional Subset Sum: looking for information. Also, your problem has been proved to be NP-hard if we allow the requirements to include large numbers: What algorithms exist for solving natural number linear systems?. (In technical terms, the problem is NP-hard when the macro-nutrient requirements and properties are provided in binary. I don't know if it remains NP-hard when they're provided in unary -- and the latter seems more relevant for practical situations.)