1
$\begingroup$

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?

  • 0
    Where is this problem from?2011-02-11
  • 0
    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.2011-02-11
  • 0
    Sorry for being so late, but what game was this?2017-11-09
  • 0
    @Zimano It was too long ago to remember today, sorry2017-11-10

3 Answers 3

1

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.

0

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

  • 0
    The problem is that the simplex is in discrete space.2011-02-10
  • 0
    That means that simplex boundary is not linear.2011-02-10
  • 0
    Then you have added in the bin packing problem, known to be NP-hard2011-02-10
  • 0
    Damn. So we have nothing but try every combination?2011-02-10
  • 0
    Not every combination, but many. In many cases there are algorithms that give pretty good answers quickly. You might also like http://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.2011-02-10
  • 0
    How did you derive that this problem turns into bin packing problem?2011-02-13
0

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$.

  • 0
    Isn't the number of vertices too large? How do you get $O(L^2 \cdot N^2)$?2011-02-11
  • 0
    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.2011-02-11
  • 0
    There are M recipes, and each vertex in your algorithm corresponds to a *set* of recipes, right? Why only LM vertices?2011-02-11
  • 0
    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$.2011-02-12
  • 0
    Thus enumerating all the vertices for Dijkstra's algorithm is already a full search in recipe sequence space?2011-02-12