Determining Cheapest Food Combinations (Seems like ILP problem, but also not)

[Martin III]

This is a problem I created for myself, and I've been thinking about for a while and would like some other opinions on the matter. I'm using simple numbers just for example.

The problem:
Suppose you are hungry, and you need to eat at least 10 calories worth of food to get full, and you'd like to not go very much over that (you don't want a tummy-ache!). The foods available to you are Fish and Bread. A serving of fish has 2 calories, and a serving of bread has 4 calories. However, a serving of fish costs $1 and a serving of bread costs $5. What are the cheapest ways to get full?

The solutions:
Let f be the number of servings of fish and b be the number of servings of bread. Also, let c be total calories and p be the total price.

Now we have that:
2f + 4b \geq 10

f + 5b = p

At first this seems a lot like a linear programming problem, but if you actually work it out you'll soon see that you won't find the desired results (I won't fill up space with tableaus and pivots and whatnot). And that should be obvious, because one of the items will always have a lower price to calorie ratio: the optimum result will be all of just one item.

The problem is that the desired answer is one that doesn't go much over the target number of calories, and choosing all of one item will, in most cases, go over. BUT if the problem is changed to strictly equal to, there won't always be answer given certain parameters. And the entire time, we're trying to minimize cost, but also want to allow options (all of one item is boring!)

My solution, which illustrates the problem with treating it as an LP problem, is to "brute-force" the result.
<br /> \begin{tabular}{ | c | c | c | c | }<br /> \hline <br /> t &amp; b &amp; c (2f+4b) &amp; p (f+5b) \\<br /> \hline<br /> 0 &amp; 3 &amp; 12 &amp; 15 \\<br /> 1 &amp; 2 &amp; 10 &amp; 11 \\<br /> 2 &amp; 2 &amp; 12 &amp; 12 \\<br /> 3 &amp; 1 &amp; 10 &amp; 8 \\<br /> 4 &amp; 1 &amp; 12 &amp; 9 \\<br /> 5 &amp; 0 &amp; 10 &amp; 5 \\<br /> \hline <br /> \end{tabular}<br />

So in this case, solving the corresponding LP problem would've given 5 servings of fish and no bread, giving exactly 10 calories and only 5 dollars, the cheapest combination.

But we also see that you get exactly 10 calories with 1 fish and 2 bread, and 3 fish and 1 bread. And I would want these results as a hungry person, because even though I'm trying to be cheap, perhaps I wouldn't mind paying $3 more to get some variety in my diet.

Is there a better way to calculate these combinations than by brute-force? I feel like there should be but have so far come up dry. I would like a method that could accommodate an arbitrary number of food items.

 

[moonman239]

Actually, there is a simpler way to figure it out: for fish, $1/2 = 50 cents per calorie, for bread, $5/4 = $1.25 per calorie. The fish is cheaper.

 

[Gerenuk]

Indeed, here it is quite easy to solve. I once had the same idea but for
protein, carbohydrate, fat and sugar intake. Or even the same for vitamins. Maybe Martin is interested in doing that? :)

Btw, did you know that all kinds of cabbage are by far the cheapest providers of vitamin C? :D

 

[Redbelly98]

But we also see that you get exactly 10 calories with 1 fish and 2 bread, and 3 fish and 1 bread. And I would want these results as a hungry person, because even though I'm trying to be cheap, perhaps I wouldn't mind paying $3 more to get some variety in my diet.

Well, you could always impose the constraint that you must order at least one serving of each item.

In fact, problems similar to this one involved imposing several constraints and then figuring out how to either minimize or maximize some linear function (like cost) of the variables involved. For example, the list of constraints might look something like this:

1. At least 1 of each item.
2. Total Calories ≥ C_min
3. Total fat ≤ F_max
4. Total cholesterol ≤ Ch_max
5. etc.

If you're new to linear optimization problems like this, here's a reasonable place to get started:
http://en.wikipedia.org/wiki/Simplex_algorithm

 

[Martin III]

Actually, there is a simpler way to figure it out: for fish, $1/2 = 50 cents per calorie, for bread, $5/4 = $1.25 per calorie. The fish is cheaper.

Yes, that will result in answers that I don't want. Let me refer back to my original post to answer you:

And that should be obvious, because one of the items will always have a lower price to calorie ratio: the optimum result will be all of just one item.

Well, you could always impose the constraint that you must order at least one serving of each item.

In fact, problems similar to this one involved imposing several constraints and then figuring out how to either minimize or maximize some linear function (like cost) of the variables involved. For example, the list of constraints might look something like this:

1. At least 1 of each item.
2. Total Calories ≥ Cmin
3. Total fat ≤ Fmax
4. Total cholesterol ≤ Chmax
5. etc.

If you're new to linear optimization problems like this, here's a reasonable place to get started:
http://en.wikipedia.org/wiki/Simplex_algorithm

I thought of this, but it doesn't feel quite flexible enough. For one, I still might want the option of all of one food item, and two, I might want options with more than one required. By adding more restraints I cut out sections of results that I might be interested in.

As an aside, I'm not new to the simplex method :) Those were the tableaus and pivots to which I referred in my original post. The simplex method isn't, however, quite what I need for this problem, because I'm looking for integer numbers of servings. I could use it to get reasonable estimates, of course. (http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns)

My method (which I realize I didn't really describe, just showed the results) is to set all but one of the foods to 0 servings, and find out the minimum number of servings of the nonzero food that makes the calories greater than the target calorie count. Then I subtract one from that, and increment one of the other foods, and so and and so forth, until I find all of the good options.

I'm thinking about this from a computational perspective; if I calculated it with some linear programming library I'll get a lot of library overhead (restricting to integers is especially computationally intensive). If I use my brute-force method, I'll get superior results but it doesn't scale well. I haven't actually written any software or algorithms, but I'd imagine it's O(n!) because of its combinatoric nature.

If it wasn't obvious, I'm interested in implementing this in software, so it's to my advantage to find a more efficient way. I think it could be a really interesting project (even if no one thinks it's worth using). Anyone have other ideas?