Take the 2-minute tour ×

Consider an alchemist that has many ($N$) sorts of ingredients in his possession. Initial amounts of each of the ingredients is expressed by vector $C^0=(C_1, C_2, \dots, C_N)$.

Alchemist knows several ($M$) recipes of ingredient transmutation, expressed as a set of recipes: $R=\{ R^1, R^2, \dots, R^M\}$. Each recipe $R^i$ is a vector that describes the reagents and the products: $R^i=(R^i_1, R^i_2, \dots, R^i_N)$ such that if $R^i_j, i \in [1 \dots M], j \in [1 \dots N]$ is zero, that means $j'th$ ingredient is not used in mutation, if it is positive, than the ingredient appears in that quantity as a product of a mutation, and if it is negative, than it's quantity is consumed in mutation.

Thus, a single mutation can be expressed as a vector sum: $C^1=C^0+R^i$, where $C^0$ are ingredients before mutation, $C^1$ - after mutation, $R^i$ - mutation recipe.

Consider that we have a market where ingredients are traded. Market prices are fixed and are described by a value vector $v=(v_1, v_2, \dots, v_N)$. Thus, a value of the alchemist's supplies on the $k$-th step can be expressed as a dot product: $V^k=(C^k \cdot v)$.

Question: having the initial supply of ingredients $C^0$, book of recipes $R$ and market prices $v$, how can the alchemist derive such sequence of $L$ mutations $S=(S^0, S^1, S^2, \dots, S^L), \forall t : S^t \in R$ that the price $V^L=(C^L \cdot v)$ of the final set of products $C^L=C^0+S^1+S^2+\dots + S^L$ would be maximal?

share|improve this question
Where is this problem from? –  ShreevatsaR Feb 11 '11 at 10:35
It's from real computer life. The closest case was the browser game with tetris-like action based on ingredients stacking. After the end of the game player received a small amount of different ingredients according to his game process. Ingredients could be smelted in the cauldron to obtain items. The most valuable item was the ticked that allowed the player to play again (the game had the restriction of one game per day). To smelt the ticket one should have figured out how to cook other basic items to reach the ticket with least wasted ingredients. –  mbaitoff Feb 11 '11 at 11:21

3 Answers 3

up vote 1 down vote accepted

If you want to solve it via linear programming, you have to make it an integer linear problem.

You could for example define the (boolean) vectors $s^t_i \in \{0, 1\}$ that are 1 when recipe $i$ is applied at time $t$ and 0 if it is not applied.

You then have to add the constraint that $\sum_i s^t_i = 1 \forall t$, in words: Use exactly one recipe at a time.

The next constraint to be added is that $C_j + \sum_i \sum_{t' = 1}^{t} s^{t'}_i R^i_j \geq 0 \forall t, j$, in words: Ingredients can never exist in negative amounts. This is a linear constraint since $R^i_j$ are constants.

Then optimise for $V^L$. You can use e.g. the Gnu Linear Programming Kit to implement this problem.

share|improve this answer

This is precisely the standard linear programming problem. Any text will discuss it in detail.

share|improve this answer
The problem is that the simplex is in discrete space. –  mbaitoff Feb 10 '11 at 15:34
That means that simplex boundary is not linear. –  mbaitoff Feb 10 '11 at 15:41
Then you have added in the bin packing problem, known to be NP-hard –  Ross Millikan Feb 10 '11 at 16:41
Damn. So we have nothing but try every combination? –  mbaitoff Feb 10 '11 at 18:21
Not every combination, but many. In many cases there are algorithms that give pretty good answers quickly. You might also like portal.acm.org/citation.cfm?id=1631221, which points out that these problems are often not hard. It may be obvious that you are limited by one ingredient, so should just optimize for that. –  Ross Millikan Feb 10 '11 at 18:31

Since the market prices are fixed and $V^L = C^0 \cdot v + S^0 \cdot v + S^1 \cdot v + \ldots + S^L \cdot v$, you can also assign a value $R^i \cdot v$ to each recipe and use Dijkstras algorithm.

The exact implementation works as follows:

  • A vertex in the graph is represented by some choice of $n \leq N$ recipes. (You can identify to vertices if the same recipes were chosen in a possibly different order.)

  • Two vertices are connected by a directed edge if it is possible to go from one vertex to the next by using one recipe. At this point, one has to take into account that $C^i_k \geq 0$, because if we run out of an ingredient, it is not possible to use it.

  • Each edge gets a weight of $O - S \cdot v$ where $O$ is an offset such that all weights are positive (otherwise Dijkstra won't work here) and $S$ is the recipe applied along the edge.

  • Identify all vertices that are L steps away from $C^0$ and make this vertex the target vertex.

  • Let Dijkstra's algorithm find the shortest way. It has length $L \cdot O - V^L$.

share|improve this answer
Isn't the number of vertices too large? How do you get $O(L^2 \cdot N^2)$? –  ShreevatsaR Feb 11 '11 at 10:37
Sorry, typo. It's $\mathcal{O}(L^2 \cdot M^2)$. There should be at most $LM$ vertices. Dijkstra runs at most quadratically with the number of vertices. –  Turion Feb 11 '11 at 10:45
There are M recipes, and each vertex in your algorithm corresponds to a set of recipes, right? Why only LM vertices? –  ShreevatsaR Feb 11 '11 at 19:33
I see my error. Each vertex corresponds to a product of recipes, where recipes form a commutative semigroup. So an easy upper bound for the number of vertices is $1 + M + M^2 + \ldots + M^L = \frac{M^{L+1} - 1}{M - 1} \approx M^L$ and not $ML$. –  Turion Feb 12 '11 at 12:33
Thus enumerating all the vertices for Dijkstra's algorithm is already a full search in recipe sequence space? –  mbaitoff Feb 12 '11 at 19:25

Your Answer


