Skip to main content

Complexity reduction makes the algorithm slower

Answered

Comments

5 comments

  • Florian Kaltwasser
    Gurobi-versary
    First Comment
    First Question

    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 Gurobi Staff

    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
    Gurobi-versary
    First Comment
    First Question

    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 Gurobi Staff

    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
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    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.