Calculating path for most efficient use of consumable items?

Question

What concepts or technologies can help me with the following problem?

You have a finite inventory of resources and a list of recipes to convert a set of resources into another resource (IE "crafting" in a video game). Given that data I would like to compute an optimal path to a goal of a set of resources. For example, you have 30 items which at the end of crafting you want to end up with 5 highly complex items which may take multiple "hops" to achieve. What is the optimal recipe order to get there?

The closest concepts I can think to this are a dependency graph or scheduling algorithm but my research hasn't been helpful to deal with the consumable aspect of the resources. I imagine this is a solved problem as it is at the root of most construction jobs.

Any terms that I can Google to help me on my way. I'll be using Python or JavaScript for my project so any libraries that come to mind would be helpful too!

• Wandering Logic: Some terms that might help: state space search, automated planning and constraint satisfaction problem. I'm not an expert but I'd construct an (implicit) graph of states (each state is a set of currently available resources) with transitions corresponding to recipes, and then do some kind of heuristic search of that graph.

Answer 1

This should be solvable with integer linear programming.

Let me assume that you can borrow resources from someone if you need to, as long as you pay them back fully. Then it can be expressed in a particularly clean way as integer linear programming.

Suppose there are $d$ resources; then the current state of your inventory can be represented as a vector $v \in \mathbb{Z}^d$ that counts how many of each resource you have (negative means you owe that many). Also, each recipe can be represented as a vector $r \in \mathbb{Z}^d$ as follows: $r_i > 0$ means that this recipe creates $r_i$ many copies of resource $i$; $r_i < 0$ means that this recipe consumes $-r_i$ many copies of resource $i$.

Let $v_0$ denote your original inventory. Your goal is to find a sequence of recipes so that the inventory becomes $v$, satisfying some constraint (such as that $v_7 \ge 1$ and $v_9 \ge 1$, if you want to end up with at least one of resource 7 and 9). If $r_1,\dots,r_k$ are the available resources, it turns out this problem is equivalent to trying to find integers $x_1,\dots,x_k \in \mathbb{Z}$ such that $x_i \ge 0$ and

$$v = v_0 + \sum_{i=1}^k x_i r_i$$

satisfies the constraint. Notice that $v_0$ and $r_1,\dots,r_k$ are known, so the final inventory $v$ can be expressed as a linear function of $x_1,\dots,x_k$. Now if the constraint on $x$ can be expressed as linear inequalities (as it can in your situation), then this is an instance of integer linear programming: we want to find $x_1,\dots,x_k$ that satisfy the linear inequalities.

So, you could create this linear programming instance, then use an off-the-shelf ILP solver to solve it. The solution will tell you how many times to apply each recipe.

There is one potentially undesirable aspect of this approach: the sequence of recipes may temporarily leave with an inventory $v$ where you have a negative number of some resource. If you're allowed to borrow resources, you can think of this as representing a borrowed resource, and it's no problem; you can add the constraint $x_i \ge 0 \forall i$ on the final inventory, and that ensures that you'll be able to return all borrowed resources.

However, if you have no way to borrow resources, then the problem is trickier. You can solve it by introducing $k$ variables per time step, indicating which one of the recipes you apply in that time step. However, this blows up the size of the integer linear program by a factor of the number of steps needed, which might make the ILP solver significantly slower. You'd have to try it to see if it achieves acceptable performance in your setting. I don't know if there is a better solution -- it seems like there ought to be one, but I don't know.