Skip to main content

Adding duplicate lazy constraints in Gurobi

Answered

Comments

2 comments

  • Tobias Achterberg
    Gurobi Staff Gurobi Staff

    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
  • Michael Hamann
    Gurobi-versary
    First Comment

    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

Please sign in to leave a comment.