4
$\begingroup$

I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an analogue for the rest of the question. For the few who benefit from this information: the game I'm referring to is Magic The Gathering, and the problem is finding whether or not a set of lands can cast a given card.

We can think of the materials as steel and wood. Any resource produces a combination of them. For example:

Requirement: 1 steel + 2 wood
Resources:
- 1 steel + 1 wood
- 1 wood
Verdict: POSSIBLE

There may be generic requirements, which can be fulfilled by whatever resource is available.

Requirement: 2 ANY + 1 wood
Resources:
- 1 steel
- 1 wood
- 1 wood
Verdict: POSSIBLE

Resources may be used to produce different combinations at will, when stated of course.

Requirement: 1 steel + 1 wood
Resources:
- 1 steel
- 1 steel OR 1 wood
Verdict: POSSIBLE

Finally, there may be costs associated with certain production. Here marked as cost -> production. Costs are production specific.

Requirement: 2 steel
Resources:
- 1 steel
- 1 wood
- 1 wood -> 1 steel OR 0 -> 1 wood
Verdict: POSSIBLE

Now, given a set of these resources it is relatively easy to figure out if a given requirement can be fulfilled. What I have currently is a naïve exhaustive search with one optimisation (step 1). In pseudo-python it goes as follows:

1. produce with resources that have only one production and no cost to have current "production"
2. can_fulfill(requirement, current production, resource list)

def can_fulfill(requirement, production, resources):
    for i, resource in enumerate(resources):
        remaining = resources[:i] + resources[i + 1:]
        for cost, gain in resource:
            if can_subtract(production, cost):
                new_production = production - cost + gain
                if fulfilled(requirement, production):
                    return True
                recur = can_fulfill(requirement, new_production, remaining)
                if recur:
                    return True
    return False

It does work, and for single-production resources it is lightning fast. But in this particular case there can be many resources with multiple production options, which slows the calculation. I think the exhaustive search is my only option, because one can't know which productions ultimately lead to the fulfillment of a requirement, but could there be more clever optimisations I could implement?

My parameters are somewhat conservative for these kinds of optimisation problems I think: I expect to have up to twenty resources, each with up to eight - typically three different productions. In the game there are five production types (steel, wood and 3 more).

$\endgroup$
10
  • 1
    $\begingroup$ This might be NP-hard, in which case there is no always-efficient algorithm. In any case it can be nicely represented as an ILP problem: If card $i$ can be 3 steel or 5 wood, you add 2 variables, $x_{is}$ and $x_{iw}$, and the constraint $x_{is}/3 + x_{iw}/5 \le 1$. The goal for each resource type is expressed as a constraint that the sum of all variables of that type is $\ge$ the target value for that type. Even a free ILP solver should solve such problems quickly, but if not, you can quickly solve the LP relaxation instead: If it has no solution, then nor does the original problem. $\endgroup$ Oct 7, 2020 at 23:52
  • $\begingroup$ (The LP relaxation allows variables to take fractional values, and it may be that the only solutions have at least some variable non-integer: That is why an LP solution does not imply an ILP solution.) $\endgroup$ Oct 7, 2020 at 23:53
  • $\begingroup$ I don't understand how costs interact with OR. Can you give the general form of a rule? $\endgroup$
    – D.W.
    Oct 8, 2020 at 3:58
  • $\begingroup$ If you want to solve this in practice, can you give any idea on the sizes of various parameters? How many rules, how many resources, how many options in each rule, that sort of thing? It might be NP-hard in general but solvable in practice. $\endgroup$
    – D.W.
    Oct 8, 2020 at 4:04
  • 1
    $\begingroup$ @Felix In general, I think I would use (integer) linear programming only if there is no more specific algorithm for my problem. Linear programming feels to me personally like a catch-all for when there is no more specific algorithm. This is because ILP is NP-hard, but many problems aren't actually that hard or have at least a more performant algorithm available. $\endgroup$
    – kutschkem
    Oct 8, 2020 at 12:19

1 Answer 1

2
$\begingroup$

I suspect this may be NP-hard in general but probably feasible to solve efficiently in practice for the parameter sizes you discussion.

I will suggest an approach based on comments from j_random_hacker. One plausible approach is to express this as an integer linear programming problem. Let $a_{im}$ be the amount of material $j$ you have after the $i$th step of applying sources, $b_{ir} = 1$ if you apply resource $r$ in the $i$th step or 0 otherwise, and then write constraints to express that each step obeys the rules you've followed. See Express boolean logic operations in zero-one integer linear programming (ILP) for some general techniques for that. For instance, you'll have a requirement that $a_{im}\ge 0$ for all $i,m$; that $\sum_i b_{ir} \le 1$, that $\sum_r b_{ir} = 1$; and so on. If you have a resource that contains multiple alternative combinations, treat each as its own resource and then add a constraint that if you pick one of those combinations in any step you can't pick any of the others ($\sum_i \sum_{r \in R} b_{ir} \le 1$, where $R$ is the set of all combinations associated with a single resource). If resource $r$ is "1 wood -> 1 steel", then we'd obtain a rule like

$$b_{ir}=1 \implies\\ (a_{i-1,\text{wood}} \ge 1 \land a_{i,\text{wood}} = a_{i-1,\text{wood}} - 1 \land a_{i,\text{steel}} = a_{i-1,\text{steel}}+1).$$

Then, convert that to an ILP constraint using the techniques at the link above.

Finally, you can apply an off-the-shelf ILP solver to search for a solution.

Note that the order in which you applies resources matters, because you can never go negative on any material, which complicates the ILP instance a little bit and requires you to have a separate copy of each variable per step.


If you prefer to adjust your exhaustive search, there may be ways. One possibility is to use branch-and-bound to prune off some parts of the search space. At any intermediate point in your search, you can get a simple bound on whether it's possible that a solution could exist from here by picking a single material, say wool, counting how many wool you already have, counting how much more wool you could possibly make if you used every remaining wool-producing resource to produce the maximum amount of wool (assuming optimistically all its preconditions can be met), and checking whether that would give you enough wool to meet the target. If not, then there's no point continuing the search from here; you can prune the search. Another way to get a simple bound is to look at the total number of materials, ignoring their type (e.g., total amount of mana, ignoring color); then using each resource that you haven't used so far that increases the number of mana (assuming optimistically that it can be used), and check how much mana total that would give you; if that's not enough for your target, then you can prune the search.

However, ILP solvers already use branch-and-bound, and they are probably doing something that generalizes this and is more powerful. So, rather than implementing branch-and-bound yourself with some limited set of bounds, I suspect it might be more powerful to use a full ILP solver.

$\endgroup$
5
  • $\begingroup$ Thanks a bunch! Honestly, I should have known it would boil down to this kind of problem. Could you ellaborate a bit more on the last paragraph, about having a separate copy of each variable? If I were to formulate it as an ILP problem and use a ready-made solver, wouldn't the optimisation process be out of my reach at that point? I may have misunderstood though. $\endgroup$
    – Felix
    Oct 8, 2020 at 6:48
  • $\begingroup$ @Felix, sorry about the confusing comments. My last paragraph was implicitly a statement that I think it's a little more complicated than Discrete Lizard's earlier comments. My proposed formulation in the second paragraph already makes a separate copy of each variable; that's the primary way in which it differs from Discrete Lizard's suggestion. I suspect the optimization process won't be out of your reach. The only way to know for sure is to test it, but it's not unusual for people to solve ILP instances with thousands or tens of thousands of variables. $\endgroup$
    – D.W.
    Oct 8, 2020 at 7:47
  • $\begingroup$ I see! Did you mean j_random_hacker, in the question's comments? And by out of my reach, I simply meant that given the constraint arrays, one could not affect the way an optimiser solves the problem or the variables that it uses, which was my first interpretation of "having a copy of each variable per step". A simple misunderstanding. Yeah, I agree that this is a relatively small-scale problem. Anyways, thanks again! $\endgroup$
    – Felix
    Oct 8, 2020 at 7:56
  • $\begingroup$ @Felix, Oops, yes, I meant j_random_hacker! Sorry, my mistake. I edited the answer to add a little more at the end about an alternative approach if you don't want to use an ILP solver, and why I didn't suggest it. $\endgroup$
    – D.W.
    Oct 8, 2020 at 7:56
  • $\begingroup$ Much appreciated! I think I'll stick to the ILP as you suggested. No need to reinvent the wheel. $\endgroup$
    – Felix
    Oct 8, 2020 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.