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
    @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
    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
    Thus enumerating all the vertices for Dijkstra's algorithm is already a full search in recipe sequence space?2011-02-12