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?


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.