Which algorithm to use to solve this optimization problem?

Question

• I have items called 'Resources' from 1 to 7.
• I have to use them in different actions identified from 1 to 10.
• I can do a maximum of 4 actions each time. This is called 'Operation'.
• The use of a resource has a cost of 1 per each 'Operation' even if it is used 4 times.
• The following table indicates the resources needed to do the related actions:

|        |            Resources             |
|--------|----------------------------------|
| Action |  1 |  2 |  3 |  4 |  5 |  6 |  7 |
|--------|----------------------------------|
|     1  |  1 |  0 |  1 |  1 |  0 |  0 |  0 |
|     2  |  1 |  1 |  0 |  0 |  1 |  0 |  0 |
|     3  |  1 |  0 |  1 |  0 |  0 |  1 |  0 |
|     4  |  0 |  1 |  0 |  0 |  0 |  0 |  0 |
|     5  |  1 |  0 |  1 |  1 |  0 |  1 |  0 |
|     6  |  1 |  1 |  1 |  0 |  0 |  0 |  0 |
|     7  |  0 |  1 |  0 |  0 |  0 |  0 |  0 |
|     8  |  1 |  0 |  1 |  0 |  1 |  0 |  0 |
|     9  |  0 |  1 |  0 |  1 |  0 |  0 |  0 |
|    10  |  1 |  1 |  1 |  0 |  0 |  0 |  1 |

The objective is to group all the 'Actions' in 'Operations' that minimize the total cost. For example, a group composed by actions {3, 7, 9} needs the resources {1, 2, 3, 4, 6} and therefore has a cost of 5, but a group composed by actions {4, 7, 9} needs the resources {2, 4} and therefore has a cost of 2.

It is needed to get done all the actions the most economically.

Which algorithm can solve this problem?

Answer 1

A possible approach would be starting by grouping the actions into all possible groups. For 30 actions grouped in a maximum of 6 this would mean: $$ C^{30}_6 + C^{30}_5 + C^{30}_4 + C^{30}_3 + C^{30}_2 + C^{30}_1 = 768 211 $$ Operations.

Then, I would define the constraints to simplify the problem, as in a Constraint Satisfaction Problem (CSP). The main constraint that you have is that one action can only be represented in one Operation. So, if you choose 1 of the 768ks operations to start with, the second option will be restricted by the condition.

Then I would do some sort of planning and sum the costs until the end doing a depth-first search. Whenever I find a total cost better the previous best, you would update the best value. (Remember that the search ends when between all the operations used, all the actions were explored once.)

While doing the search the costs are added up on the go. You can precompute a vector with the same size as the number of operations where each value corresponds to the total cost of the operation, and then sum it as you are going down the path.

You should also add some heuristic to prevent checking the same operations in different orders. For example doing operating [2,3,4] followed by [7,10], where each number represents an action, is the same as doing: [7,10] followed by [2,3,4].

Answer 2

I have finally abandoned the idea of ​​doing it with an exact method and I have passed to the heuristic. I have mixed multi-boot, local search and certain random movements. Apparently this is called Greedy Randomized Adaptative Search Procedures (GRASP)

Hypothesis: the best solution is reached filling the 'operations' with the maximum of 'Actions' per 'Operation'. Other combinations are more expensive

1. create a random solution
   [[1 2 3 4] [5 6 7 8] [9 10]]

2. calculate the cost of each 'Operation'
   [[6] [6] [5]] == 17

3. Study the posibility of minimize the lower 'Operation' permuting some 'Action' with the other 'Operations'.
   Actions 4 & 7 permute with 9 & 10
   [[1 2 3 9] [5 6 10 8] [4 7]]

4. Calculate the new cost
   [[6] [7] [1]] == 14

5. Repeat steps 2 to 4 until it is not possible to minimize the lower, then the second lower, then the third etc

6. You will find soon a Local Minimum. If no more moves are allowed but the Local Minimum is not the Global Minimum, permute two random 'actions' between two random 'operations' and repeat the steps 2º to 5º.

With this method it is possible to find very fast a solution adjusted to the minimum global cost with a complexity of O(n·log(n)), where n is the amount of 'actions'

I've tested it with a random sample of 60 'actions' and 26 'resources' grouped in 'operations' of 6 'actions'. It toke arround 5 minutes to get a really good solution arround 40% better that the initial one (*), and 30 minutes after it only got better solution in about 1%

(*) the initial solution was not actually a random solution. Instead of that I used 'Ant Colony' algorithm with 15 ants to get a better initial solution and reduce the amount of iterations, but that is another history