0
$\begingroup$

I have a programming problem, instead of describing the whole domain it's easier for me to create an analogy. The numbers I use in this example are completely arbitrary.

Your cousin is coming over later and you must feed him dinner. He will only eat what he randomly decides he wants when he gets to your house and will not tell you ahead of time what that will be. However, you have been given a list of recipes that you know for certain he will choose from.

All of the recipes are soups that are made from one or more ingredients and the recipes call for small, medium, or large cans of each ingredient. There are no rules for how many cans are required or what sizes they can come in, but you don't care about waste so it's fine if you use a can that is larger than the recipe calls for.

Your cousin isn't very strict about sticking to the recipe, in fact, only half of the ingredients have to even be in the pot for him to call the recipe complete!

Unfortunately you have exactly zero of the ingredients needed and you only have time to make a short shopping trip before he arrives. Additionally, the store you're shopping at will only allow you to leave if you have exactly 5 small cans, 4 medium cans and 3 large cans. Once again, you don't care about waste so getting extra, unused cans is perfectly okay.

Since you don't know what recipe you'll be demanded to make, you want to try to be prepared to cook as many recipes as possible, but because of the restrictions on number of cans you can buy you will not be able to buy all of them.

I am attempting, essentially, to find an algorithm that takes the list of recipes and then suggests a shopping list that covers the maximum number of recipes.

Summary of rules

  • Demanded recipe is random
  • You only need to adhere to 50% of the ingredients called for
  • You must buy exactly 5 large cans 10 medium cans and 20 small cans
  • Waste is fine, using cans larger than needed or buying extra cans is okay
  • Using larger cans does not constitute completing the recipe more than smaller cans
  • For example: A 3-ingredient recipe is still only 33% complete from one can regardless of size.
  • You will be asked to prepare exactly one recipe, no more
  • Currently there are 25 recipes on the list, but more get added each time your cousin visits!
  • There are no recipes with more than 15 ingredients, some have zero ingredients but we just ignore them
  • Practically there's probably around 75 ingredients among the recipes

My attempts

My first idea was to iterate through the ingredients and rank them on how much they contribute to each recipe. For example, if a recipe calls for 10 ingredients then our ingredient would have 0.1 added to it's score. If another 2-ingredient recipe used that ingredient it would have a score of 0.1 + 0.5 = 0.6

Each ingredient would have a rank for each can size (Small, Medium, Large)

I would then consider each ingredient by summing the size ranks up to a given size. So for example I would add the Small + Medium + Large ranks together and sort the ingredients on that sum to decide which ingredients I would buy large cans of. Then I would remove those ingredients from the list and do the same thing with Small + Medium ranks.

Then I realized if there were 20 recipes with one ingredient in common, but none of the other ingredients were used anywhere else (even among the 20 recipes) then we would have one ingredient with a huge rank which couldn't even satisfy one recipe.

Then I thought it would be good to include a commonality factor into my calculations: An ingredient would also be ranked on the commonality of it's "friends". An ingredient is "friends" with another if they share the same recipes. If an ingredient has low ranking or uncommon friends then it should rank low too.

I just now realized I might be coming at this backwards, maybe I should compare how much the recipes have in common. If a recipe has a lot in common with many other recipes then covering it will probably cover all of the recipes similar to it.

Any ideas on how to find the solution to this? I cannot believe there hasn't been a graph theory problem similar to mine somewhere out there. I just haven't found it yet.

$\endgroup$
  • $\begingroup$ Can you state your problem more succinctly? $\endgroup$ – Yuval Filmus Aug 1 '17 at 6:25
  • $\begingroup$ What's the context in which you encountered this problem? Are you looking for a practical solution, or do you want to know its theoretical complexity? If the former, about how many ingredients do you expect there to be, and about how many recipes? $\endgroup$ – D.W. Aug 1 '17 at 6:31
  • $\begingroup$ Thanks for the edit. How many total ingredients are there (over all the recipes)? i.e., if you count the number of ingredients that appear at least once in some recipe, how many are there? $\endgroup$ – D.W. Aug 1 '17 at 22:55
  • $\begingroup$ I updated some of the numbers. I've found that sorting the ingredients by total recipes usually gives a pretty decent practical solution. I'm interested in the theory behind forming optimal solutions. $\endgroup$ – Muuski Aug 2 '17 at 16:54
0
$\begingroup$

Your problem sounds like the sort of thing that would be NP-complete (though I haven't proven it), so I'd expect there probably is no efficient algorithm that is guaranteed to find the optimal solution. Instead, I'd suggesting looking at Dealing with intractability: NP-complete problems for technique you could try. You'll probably be looking for some kind of heuristic. For instance, you might try simulated annealing.

You could also try expressing this as an instance of integer linear programming and applying an off-the-shelf ILP solver. I don't know if that is likely to work well, though. The resulting system of constraints will be fairly complex, and so might be too hard for ILP solvers. A possible approach to do that would be to introduce zero-or-one variables $x_{i,s},y_j,z_{i,j}$, with the intention that $x_{i,s}=1$ counts the number of size-$s$ cans of the $i$th ingredient that are purchased and $y_j=1$ means that the $j$th recipe can be prepared from the purchased ingredients and $z_{i,j}=1$ means that ingredient $i$ has been bought in sufficient quantity for recipe $j$; then add inequalities to enforce the constraints you mentioned.

$\endgroup$
  • $\begingroup$ I was worried that would be the case. I don't really have enough knowledge in this area to make that determination myself though. Thanks. $\endgroup$ – Muuski Aug 3 '17 at 16:34

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.