Complexity reduction makes the algorithm slower

Answered

Florian Kaltwasser

• July 06, 2022 08:17

Hey all,

i am trying to solve a MIP in which modules are arranged. First i had the problem set up that every module can sit in every possible place, so i have O(n) = n!

What i now tried was to change the problem to not every module can sit everywhere, for example if i have 8 modules with 4 classes in which the specific 2 modules can change place, but not every module can sit everywhere. I guessed that this should enormously reduce the complexity of the algorithm. I attached how i coded this:

This variables are set in a double for-loop. Before the Var was set by addVar(0.0 , 1.0 , 0.0 GRB.BINARY), so that every module can be in every possible place.

My Array auswahl[][] auswahl is looking the following way:

So it allows every module to sit in just 2 places, and it actually worked. But it made the algorithm much slower instead of faster.

Can anybody tell me why this is happening or how i could implement the thing i want to do so that it reduces my complexity?

 

0

• 

  Matthias Miltenberger

  Gurobi Staff

  • July 06, 2022 14:10

  Hi Florian,

  Without more information, it is difficult to say what might be causing the slowdown. Please note that you are still adding all the variables, despite fixing many of them to 0. Instead, you should not even add those variables in the first place to reduce the problem size. Gurobi should remove those fixed variables in the presolving phase but it is still a bad practice to add them - assuming you don't unfix them in a later stage of the solving process.

  I hope that helps.

  Cheers,
  Matthias

  0
• 

  Florian Kaltwasser

  • July 07, 2022 11:09

  

  

  

  Hello Matthias,

  thank you very much for your answer, i got your point. Unfortunately if i completely leave out every variable of the array p[] which has a 0 for the upper bound in the array auswahl[] i have to separate p[] into 4 separate arrays and need 4 loops for every loop of p[] which won´t solve my complexity problem. Is there any possibility to keep working with the array p[][] but define all the variables i don´t need in another way? I  tried just setting them to 0, but obviously this does not work because i need to define them as a gurobi variable.

  I hope you get what i mean, thank you very much for the support and kind regards,

  Florian

  0
• 

  Matthias Miltenberger

  Gurobi Staff

  • July 07, 2022 11:16

  Hi Florian,

  I am not entirely sure I understand the complexity issue. Can't you just loop over all p values but only add a variable if the corresponding p[i][j] value is non-zero?

  On a related note: If you are having difficulties building your model because of its complexity, you will most likely run into issues solving it.

  Cheers,
  Matthias

  0
• 

  Florian Kaltwasser

  • July 19, 2022 10:13

  

  

  

  Hi Matthias,

  the complexity issue is the following: if i have 8 modules that can be placed in all of the 8 possible positions, i have 8! possible ways to permutate the modules in the position. This way my program has to find the best solution for all 8! possible ways to arrange the modules. I want to allow 2 modules to just be placed in 2 defined positions. So for me then i dont have 8! possible arrangements but 28. If i only add the variables for the possible positions i get an exception because the other variables are not initialized. I already tried setting up constraints instead of defining the variables differently, but this did not make the solver faster anyways. Is there a possibility to manage the permutation via the callback codes? By now i am pretty desperate as i tried many ways to solve the problem but did not manage it yet.

   

  Thanks for your support in advance

  Best regards

  Florian

  1
• 

  Matthias Miltenberger

  Gurobi Staff

  • July 22, 2022 11:19

  Hi Florian,

  many combinatorial problems have an exponentially large search space and even exponentially many variables. One needs to be careful when formulating the problem to avoid this issue.

  A nice example is the TSP: You cannot explicitly add all possible subtour combinations and exclude them via constraints - instead, you add them during the solving process whenever necessary. Please check out our Python example that demonstrates how to implement this: tsp.py (gurobi.com)

  In any case, if you only add the variables you really need, you also need to take care to not reference non-existing variable indices when constructing the constraints.

  I hope that helps.

  Best regards,
  Matthias

  0

Please sign in to leave a comment.