Adding duplicate lazy constraints in Gurobi

Answered

HAONAN ZHONG

• September 07, 2019 18:32

My program will add a lazy constraint that may have been added to the model in the previous node. In this case, will Gurobi automatically identify and ignore the lazy constraint? Do I need to keep track of added constraints to make sure no duplicate constraints are added?

Thank you!

2

• 

  Michael Hamann

  • October 17, 2019 15:31

  

  

  If you say "node", do you mean in a GRB_CB_MIPNODE callback or in a GRB_CB_MIPSOL callback?

  In the context of a GRB_CB_MIPSOL, you definitely need to add constraints even if you have added the exactly same constraint before if you want to cut off the solution. The documentation explicitly says that solutions may violate lazy constraints - the only way to cut off the solution is then to simply specify the same constraint again. I experienced exactly this when using Gurobi, I cut off a solution and then the next solution violated exactly the same constraint again.

  For GRB_CB_MIPNODE, basically the same seems to be the case, it definitely happens that the constraints you added in one node are again violated in one of the following nodes. I have no idea though if it helps Gurobi here to just add the same constraints again or if this only increases the size of the model. Apart from possibly impacting the performance, I cannot imagine though that adding duplicate constraints is a problem.

  0
• 

  Tobias Achterberg

  Gurobi Staff

  • October 18, 2019 12:15

  The issue usually arises from parallel solves. In our parallel MIP solver we first process a bunch of nodes without any user interaction in parallel. Then, at the synchronization point, we present those nodes (and the potential solutions found while processing the nodes) in a sequential fashion to the user. If the user now produces a lazy constraint to cut off the solution, we discard the solution and add the lazy constraint to the model. But all the subsequent nodes from the same bunch (that have already been processed) of course still do not know about this constraint. Hence, it can happen that the same solution is found at multiple nodes. Nevertheless, duplicate lazy constraints will of course only be added once, so there is no harm. After having done the synchronization, the lazy constraint is part of the LP relaxations, and from thereon, you should no longer get solutions that violate this constraint.

  Regards,

  Tobias

   

  1

Please sign in to leave a comment.