Does Gurobi take advantage of the problem structure?
AnsweredDoes 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')

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 
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 564570 is where the difference between these two models.
Best,
Hussein0 
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 nondefault 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 MIPGapBest regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments