Maximum use of resources, taking into account several types of resources and specific mixtures of resources per task

Question

Considering

You have a very large number of possible tasks, each of which requires the use of a certain subset of possible resources from a large number of possible resources.

Each task has related resources:

Task 1

• 1 gold
• 2 silver

Task 2

• 2 gold
• 1 bronze

Task 3

• 1 bronze

And you have a set of resources available:

Resources

• 3 gold
• 2 bronzes

Problem

Choose a subset of the tasks, any of which can be performed more than once, which makes the "best use" of all available resources. In this case, perhaps we will choose "Task 2" and "Task 3", since it will leave us only 1 remaining gold. We cannot complete task 1 because we do not have silver.

Questions

This seems like some kind of optimization problem, but I'm not sure if this problem will be “triggered”. Is there any bizarre name for this that I could find to help me find possible solutions? Are there simple algorithms that solve this problem? Is it solvable in a reasonable amount of time? Are there any good heuristic approaches?

Notes

• The task, as shown, means that the resources can be weighted in different ways (that is, worse if you leave 1 gold than with 1 bronze), but this is not necessarily a problem. The solution should not take this into account, but it would be an interesting extension.
• Tasks and resources do not have to be integer values, but I'm not sure if this will make a big difference.

Answer 1

It sounds just like the problem with multiple backpacks - the only thing you need to change is to assign each element a value equal to the sum of the elements it uses, then it becomes a standard satchel, because by maximizing the amount, the remainder is minimized.

Answer 2

This problem is the type of kit packaging. It is also known as the "flight crew problem." You have a certain number of pilots, engineers, stewards, etc. And different aircraft, which require a different assortment of each type of crew. Usually, with the flight crew problem, you are looking for the exact task between personnel and aircraft, but here we want to maximize the use of personnel by choosing different types of aircraft (which are the "tasks" at the post).

In any case, how these problems, NP-hard, are solved by exhaustive search using mixed integer linear programming . See Sandia MILP Survey or MIT Aeronautics Page on MILP .

There is the SYMPHONY package, which includes a set of partitioning and packaging solvers that do this.