Does Gurobi take advantage of the problem structure?

Answered

Hussein Sharadga

• January 07, 2023 22:13
• Edited

Does Guroib take advantage of the problem structure?

I am working on a large optimization problem with more than 40,000 binary variables and huge number of constraints. below is only one of the constraints:

P_plus >= P
P_plus >= -p

That will be applied on every time step t and every node i. 

First formulation:      Gurobi consumes 1 minute to solve the model.

Second formulation: Gurobi consumes 9 minutes to solve the model.

 

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

# First formulation, efficient formulation:
for i in range(n_b):
    for t in range (n_t):
       m.addConstr(P_plus[i,t]>=P[i,t],name='c0')
       m.addConstr(P_plus[i,t]>=-P[i,t], name='c1')
       
# Second formulation, less efficient formulation:       
m.addConstrs((P_plus[i,t]>=P[i,t] for i in range(n_b) for t in range (n_t)) , name='c0')
m.addConstrs((P_plus[i,t]>=-P[i,t] for i in range(n_b) for t in range (n_t)), name='c1')

 

 

Related to

• Performance

1

• 

  Jaromił Najman

  Gurobi Staff

  • January 09, 2023 10:36

  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
• 

  Hussein Sharadga

  • January 12, 2023 07:14

  

  

  

  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

  • January 12, 2023 13:47

  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.