The bibulous sorcerer Roseacrucis has depleted the Library’s distilled reserves. You must journey to obtain the myriad ingredients necessary to recreate the seventy-seven official IBA cocktails—but your wallet runs light, and your thirst grows deep. In what order do you obtain ingredients to make the most drinks for the fewest drachma?
The sample solution given the pre-selected ingredients:
A recipe is a set of ingredients. The well-ordering problem: given a set of recipes \(r_1\ldots{}r_m\) comprised of ingredients \(y_1\ldots{}y_n\), find an ordering \(\sigma\) of the ingredients that maximizes \[ \large\sum_{i=1}^{n}\sum_{j=1}^{m} p_\sigma(i, j) \] where \[ \large p_\sigma(i, j) = \begin{cases} 1 & r_j \subseteq \{y_{\sigma^{-1}(k)} \mid 1 \leq k \leq i\} \\ 0 & \mathrm{otherwise.} \end{cases} \]
In other words, we assign one point to each recipe in each round it is satisfiable by the already-collected ingredients. We reduce the well-ordering problem to integer linear programming:
\[ \large \begin{equation} \begin{split} \text{maximize } & \sum_{k=1}^n\sum_{j=1}^m v_{k,j} \\ \text{subject to } & \begin{aligned}[t] \sum_{i=0}^{n}c_{k, i} &= k & k \in [1, n] \\ c_{k,i} &\le c_{k+1, i} & i \in [1, n], k \in [1, n-1] \\ v_{k,j} &\ge -\lvert{}r_j\rvert + 1 + \sum_{i \in r_j}c_{k,i} & k \in [1, n], j \in [1, m] \\ v_{k,j} &\le c_{k,i} & k \in [1, n], j \in [1, m], i \in r_j \\ \end{aligned} \\ \text{binary } & \begin{aligned}[t] v_{k,j} & & k \in [1, n], j \in [1, m] \\ c_{k,i} & & k \in [1, n], i \in [1, n] \\ \end{aligned} \\ \end{split} \end{equation} \]
\(c_{k,i}\) is set when \(y_i\) is collected in rounds 1 through \(k\). \(v_{k,j}\) is set if \(r_j\) is satisfiable in round \(k\). The first and second constraints ensure exactly one ingredient is added in each round. The third and fourth constraints model that \(v_{k,j} = \bigwedge\limits_{i \in r_j} c_{k,i}\).
The system is solved in-browser using jvail's port of GLPK to WebAssembly. Alternatively, COIN-OR's cbc can find the optimal solution in under thirty seconds on a desktop computer. Recipes adapted from teijo/iba-cocktails.