Optimal sequence of recipes

Question

I assume the following is/reduces to a known problem, but I haven't been able to find it.

I have a sequence of recipes with associated costs. Each recipe converts a set of resources to another set of resources.

I.e.

• () -> (1A) cost 1
• (2A) -> (1B, 1C) cost 2
• (4A) -> (3B, 1C) cost 2
• (1A, 1B) -> (1C) cost 1

I now want to find the sequence of steps that maximizes the gain of one resource (say "C") divided by the cost (or perhaps just the sequence that maximizes the gain of the resource for some limited cost).

Does this problem have a name and is there a better approach than brute force search (perhaps with some memoization)?

Answer 1

This problem can be modeled as a longest path search in a directed graph. Each vertex of the graph corresponds to a set of currently available resources (starting with the empty set), and the recipes define the possible edges from one set of resource to a new one. As weights for the edges, one should pick either

• the increasement of "# C" itself

• "# of current C / divided by the current total costs" - ""# of C after applying the recipe / divided by the total costs after the applying the recipe"

depending which of the two variants of the problem one want to solve.

For the given problem statement, the graph can be theoretically infinite, but it can be made finite by adding some reasonable restrictions like maximum costs, or a maximum number of of steps/recipes to be applied.

If the recipes are constructed reasonably, they will guarantee the graph to stay acyclic, in which case, as Wikipedia states, the problem can be solved using techniques for a shortest-path search. But beware, if there are recipes which allow the intermediate consumption of the "goal resource", resulting in negative weights. And if there are recipes which may let the graph contain cycles, this can become an NP hard problem.

Answer 2

The problem can be modeled as an instance of the covering problem (source).

Number the resources 0 to m-1 and number the recipes 0 to n-1.

Now let A_i,j be the changes from recipe j to resource i. A is now a matric of dimensions m x n. Let c_j be the cost of executing recipe j. c is a vector of dimension n.

We can now formulate the question: minimize the cost to achieve b_i items of resource i (not quite the question, I asked for, but close enough). b is a vector of dimensions m.

Let x_j be the number of times we use recipe j, x is a vector of dimension n.

We want to minimize c^T x under the constraint that Ax>=b and x>=0.

This is now the covering problem, for which there are multiple linear optimization solutions.

This algorithm ignores that the solution might be non-integer (we can just scale the solution to get an integer solution: it should be rational if the input is rational) and that the solution might temporarily dip below zero in some resources (we assume that we start with sufficient resources to handle the temporary dip in resources).