4
$\begingroup$
  • 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?

$\endgroup$
  • $\begingroup$ Is the objective to perform each action at least once? ( in one of the groups) $\endgroup$ – Miguel Saraiva Jan 7 at 14:09
  • $\begingroup$ Exactly one time all the actions $\endgroup$ – Joracosu Jan 7 at 14:11
  • $\begingroup$ If the problem is the size of the table you showed or not much bigger the best way is probably brute forcing it. What is the real size of the problem? $\endgroup$ – Miguel Saraiva Jan 7 at 14:14
  • $\begingroup$ 30 actions with 10 resources grouped in a max of 6. Only the group of 6 are 4.000.000.000 combinations, but there are also other size combinations... I couldn't calculate it but probable huge $\endgroup$ – Joracosu Jan 7 at 14:23
  • $\begingroup$ It is not that big, 30 combinations 6 is 600k, then you do the same for 30 combination 5 etc it's around 1M total. Then you just do planning, I think it is pretty feasable, I can try to write something to help you out. You don't need to count in the resources in the combinations, you just verify it during planning and count up the total cost. $\endgroup$ – Miguel Saraiva Jan 7 at 14:52
0
$\begingroup$

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].

| improve this answer | |
$\endgroup$
0
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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