Skip to main content

Does Gurobi take advantage of the problem structure?

Answered

Comments

3 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Hussein,

    Does Guroib take advantage of the problem structure?

    Yes, Gurobi tries to take advantage of problem structure such as finding independent model components, symmetry, special cases (e.g., networks).

    Does that mean I should try to aggregate the constraints applied on the same time step and node together?

    In this case, you add the exact same constraint, but in a different order. This indeed may have an impact on solver performance, cf., Is Gurobi deterministic? The ordering of constraints/variables may affect specific heuristics. Could you try experimenting with the Most important parameters, in particular with Presolve, to try to avoid the behavior? If it is not possible, could you please share two model files showing the described behavior? It would be best, if the models would be rather small. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

    Best regards, 
    Jaromił

    1
  • FirstHussein Sharadga
    Gurobi-versary
    Investigator
    Conversationalist

    Hi Jaromił Najman.

    Thank you so much for your time. 

    The model is, unfortunately, large. The two model files, however, can be found here.

    https://drive.google.com/drive/folders/1aRJ06PUTiFgQtx0zGShaCjsy9AWRnD5X?usp=sharing

    Line 564-570 is where the difference between these two models.

    Best,
    Hussein

     

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Hussein,

    Thank you for the files.

    It is indeed the case that constraint ordering does affect solver's performance. In particular it affects the paths taken by the Simplex and Barrier algorithm. You should try experimenting with Method=-1,0,1,2 to find the best setting for your given constraint ordering. For example, on my machine Method=2 worked best for MIP1 while Method=-1 worked best for MIP2.

    Additionally, you might want to set DegenMoves=0. Given the size of your model, you might also want to use a non-default MIPGap, e.g., MIPGap=0.001.

    m.setParam("Method",2) # for MIP1
    m.setParam("DegenMoves",0) # are quite expensive for this particular model
    m.setParam("MIPGap",0.001) # aim for 0.1% final MIPGap

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.