I am trying to find the best way to solve the following problem:
A cook has to prepare $n$ dishes, and for each dish he has $k$ different recipes. Each recipe is a non-empty subset of the set $I$ of all ingredients.
How can we find the smallest set of ingredients required to prepare all dishes?
I can currently write this problem as an instance of other, more general problems but I was wondering whether there's a precise, well-known name for this problem.
Here's a small example: let's say you have 5 possible ingredients $a, b, c, d, e$ and three dishes.
- Dish 1 can be prepared with either recipe $\{e\}$ or with $\{b, c\}$
- Dish 2 can be prepared with recipes $\{e\}$ or $\{a, c\}$
- Dish 3 can be prepared with recipe $\{a, b, c\}$ or $\{a, b, d\}$
You can prepare all three dishes with ingredients $\{a, b, c\}$. Ingredients $d$ and $e$ are not required in the optimal case. A greedy algorithm would have picked recipe $\{e\}$ and end up on a sub-optimal solution. And while in this case there is a recipe that includes all previous ingredients, this is not expected to be the case in general.
Some things I looked into that didn't quite work:
- Set cover: doesn't quite fit because it is okay for some ingredients not to be used at all, like $d$ and $e$ in the example.
- Assignment problem: it typically doesn't account for a single ingredient being used in multiple dishes.
- 0-1 Knapsack problem with multiple choice constraints: the formulation of the problem is the same, but it doesn't account for the "weight" of each element changing based on what's already in the knapsack: if you put recipe $\{a, b, c\}$ in the knapsack, the cost of adding recipe $\{b, c\}$ is 0.
- This question is very similar to mine, but I could't get pass the problem that getting the ingredients for half of recipe 1 and half of recipe 2 doesn't mean that I have a complete recipe.
You can solve the problem via integer linear programming as follows. Let $I_{d,r} \subseteq I$ be the set of ingredients required for dish $d$ and recipe $r$. Let binary decision variable $x_{d,r}$ indicate that dish $d$ uses recipe $r$. Let binary decision variable $y_i$ indicate whether ingredient $i$ is used. The problem is to minimize $\sum_{i\in I} y_i$ subject to \begin{align} \sum_{r=1}^k x_{d,r} &= 1 &&\text{for $d\in\{1,\dots,n\}$} \tag1\\ x_{d,r} &\le y_i &&\text{for $d\in\{1,\dots,n\}$, $r\in\{1,\dots,k\}$, and $i\in I_{d,r}$} \tag2 \end{align} Constraint $(1)$ makes sure that each dish uses one of its recipes. Constraint $(2)$ forces all the required ingredients to be used for each chosen dish and recipe.