Combinatorial optimization where several criteria must be satisfied

Question

We are a group of first-year students studying computer science.

We are working on a project called "The electronical diet plan" (directly translated)

We want to make a program in C# that on a weekly basic calculate a diet plan that fullfiels/satisfies some criteria:

Your daily energy intake should not exceed the calculated calorie needs. (Ex. If we calculate that a person should eat 2000 calories per day, the diet plan should plan approximately 2000 calories)

The daily energy (calories) should be distributed as follows:

• Fat 25-35%
• Carbohydrates 50-60%
• Proteins 10-20%

We have a "database" with food and how much fat, carbohydrates and proteins it contains + the approximate price. And we have a "database" with recipies and how much time it takes to cook it.

SO: We want to make a program that on a weekly basic calculate a good diet plan which satisfies the daily energy need (and how it should be distributed (fat, carbohydrates, proteins)). The program should also plan a diet plan that not takes a lot of time and not cost to much (the user defines a upper bound for the price pr. week).

SO.. We want help to find a method/algorithm that can combinate 3-6 dishes per day which satisfied this ^^ We have been looking at a lot of combinational optimizations algorithms/problems but mostly "The knapsack problem".

But these algorithms/problem is only satisfying one criteria or trying to find the "cheapest" solution. -> We want to satisfy a lot of criteria and want to find the best solution (not cheapest.. ex. fat has to be between 25-35%, not just be the lowest value)

We hope that some of you can help us with a good algorithm.

Answer 1

When it comes to finding the "cheapest" solution rather than the "best", you'll just have to redefine "cheap".

In optimization theory one often refers to the cost function, which is to be minimized - in your case, "cost" could be "fat percentage point difference from 30%", i.e. it costs nothing to eat 30% fat, and equally much to eat 20% as 40%. Of course, to make the method even more sophisticated, you could weigh it so it's more "expensive" to eat too much fat, than too little.

Now, if you create costs for each of your criteria, you also have to weigh them together, as mellamokb noted in a comment; to do this, simply calculate a weighted total cost. You'll end up with something like the following:

cost of diet = (importance of price) * price + (importance of time) * time + (importance of fat) * (deviation from fat goal) + etc ...

If you want to make it impossible to go over budget (in money spent), you could add terms like
over budget ? infinity : 0 to make the algorithm find solutions within the budget. You can also make constraints for repetition of meals etc - it's more or less your imagination (and computing power) that set the limits.

Now that you have a cost function, you can start working on your solution to the problem: minimizing the cost of the diet. And suddenly all those algorithms finding the "cheapest" solution make sense... ;)

---

Note that formulating this cost function is usually the difficult part. Depending on how you weigh your costs you'll find very different solutions to the problem; not all of them will be useful (in fact most of them probably won't be).