Skip to main content

Lazy constraint in MIPNODE and MIPSOL

Awaiting user input

Comments

5 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Cero,

    I am not sure if I understand your issue correctly so I added a couple of questions.

    If I assure that in MIPSOL the violated constraints will be added as lazy constraints, will it be a problem if I treat these violated constraints in MIPNODE as user cut? Since the user cuts(indeed lazy constraints) should be valid inequalities to the "original" problem, which is true for my real problem but not the problem I give to gurobi( I treat some constraints by lazy callback)

    Yes, there can be an issue with syncing meaning that a lazy constraint has not been added yet to all nodes while you already use it as a user cut. I don't fully understand why you would like to add the same constraint as a lazy constraint and as a user cut. If a given constraint is a lazy constraint then it is sufficient to add it as such. You refer to you "original" problem and some that you give to Gurobi. Do you mean that you are solving two models simultaneously? Could you please elaborate a bit more on this point?

    I drop these lazy constraints( dense constraints) because adding them all is too expensive, which will cause the problem to solve slowly. Is there any other advice on the performance if some constraints are too dense/hard?

    Is adding all of them too expensive because they are too many (exponential amount) or is it expensive to build the model, i.e., model building takes more time when adding those constraints? In the case that there are not exponentially many of those constraints, did you actually try adding them to the model? Often, Gurobi's presolve is able to reduce the density of constraints.

    I found in my MIP log, that in the root node, my callbacks add more lazy constraints than my total number of lazy constraints. Is that possible?

    What exactly do you mean by "my MIP log"? Do you use a print statement and a counter to show the number of added lazy constraints? Note that a lazy constraint may be added multiple times due to parallelization.

    Can you specify the callback order of MIPNODE and MIPSOL? I found that sometimes MIPNODE will be called before and after MIPSOL. Why is this situation?

    There are multiple phases of the MIPNODE callback, cf. MIPNODE_PHASE. A MIPNODE callback can be executed before MIPSOL and depending on when a feasible solution is found it is possible that a MIPNODE callback is executed after a MIPSOL callback to possibly improve the current node.

    Best regards,
    Jaromił

    0
  • ce jekl
    Collaborator
    Investigator

    Hi, Jaromił

    Thank you for your quick response.

    Yes, there can be an issue with syncing meaning that a lazy constraint has not been added yet to all nodes while you already use it as a user cut. I don't fully understand why you would like to add the same constraint as a lazy constraint and as a user cut. If a given constraint is a lazy constraint then it is sufficient to add it as such. You refer to you "original" problem and some that you give to Gurobi. Do you mean that you are solving two models simultaneously? Could you please elaborate a bit more on this point?

    No, only one model. First, I add my lazy constraints by cbLazy in MIPSOL to assure the correctness of the model, that's the normal way to add lazy constraints. Besides, I want to add my lazy constraints in MIPNODE as cut to let gurobi decide for me which is better to add to the model. They are indeed lazy constraints. I want to do this because I want to accelerate my solving process and not wait until MIPSOL happens.

    Yes, there can be an issue with syncing meaning that a lazy constraint has not been added yet to all nodes while you already use it as a user cut.

    I don't think that's a problem in my situation since

    If I assure that in MIPSOL the violated constraints will be added as lazy constraints

    Is it correct? A constraint is already a valid cut.

     

    Is adding all of them too expensive because they are too many (exponential amount) or is it expensive to build the model, i.e., model building takes more time when adding those constraints? In the case that there are not exponentially many of those constraints, did you actually try adding them to the model? Often, Gurobi's presolve is able to reduce the density of constraints.

    I originally solve this problem by adding them all into the model, but the root relaxation is too expensive and most of these lazy constraints won't be active in the final solution. They are NOT exponentially amount but they are very dense and expensive, so I want to add them as few as possible.

     

    What exactly do you mean by "my MIP log"? Do you use a print statement and a counter to show the number of added lazy constraints? Note that a lazy constraint may be added multiple times due to parallelization.

    Yes, that's exactly what I did.

     

    There are multiple phases of the MIPNODE callback, cf. MIPNODE_PHASE. A MIPNODE callback can be executed before MIPSOL and depending on when a feasible solution is found it is possible that a MIPNODE callback is executed after a MIPSOL callback to possibly improve the current node.

    I want to know more about the 3 phases of MIP_PHASE. I can understand phase 0 for NoRel heuristics before solving relaxation. What's the exact meaning of phase 1 and 2? Does phase 1 mean the solving relaxation, cut separation, and resolving, and phase 2 mean primal heuristics?

     

    Thank you for your patience, and I want to add a few questions:

    1. If I add the lazy constraints in the model, not by callback but attribute Lazy. Is it correct to set Lazy=-3? Since the doc says they will be treated as user cuts.
    2. I know that when adding a lazy constraint by cbLazy, gurobi will notify all succeeding nodes of these new added lazy constraints, Is it the same behavior for cuts? Or the cuts are only applied for the descendent/child nodes?
    3. For large num and expensive constraints, is there another way to deal with them?
    4. Is it possible to let independent/concurrent MIP models to communicate with each other?
    Best regards,
    Cero
    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Cero,

    No, only one model. First, I add my lazy constraints by cbLazy in MIPSOL to assure the correctness of the model, that's the normal way to add lazy constraints. Besides, I want to add my lazy constraints in MIPNODE as cut to let gurobi decide for me which is better to add to the model. They are indeed lazy constraints. I want to do this because I want to accelerate my solving process and not wait until MIPSOL happens.

    Adding a constraint as a lazy constraint and as a user cut will not benefit the solution process. Lazy constraints will be sorted out if they are no longer needed and handled just as user cuts would be. If you want to add a subset of your lazy constraints as user cuts, then I would recommend to add them as normal constraint. This way Gurobi's presolve can use this information to probably improve the presolved model.

    Is it correct? A constraint is already a valid cut.

    A user cut is not a usual constraint. It is added during the solution process and thus it is not allowed to cut off any integer solutions such as a lazy or a normal constraint would do. In general, I would definitely avoid adding a constraint as both a lazy constraint and as a user cut.

    I originally solve this problem by adding them all into the model, but the root relaxation is too expensive and most of these lazy constraints won't be active in the final solution. They are NOT exponentially amount but they are very dense and expensive, so I want to add them as few as possible.

    Did you try adding them all to your model? Gurobi can often reduce the density and complexity of constraints in presolve so I think it is definitely worth a try.

    I want to know more about the 3 phases of MIP_PHASE. I can understand phase 0 for NoRel heuristics before solving relaxation. What's the exact meaning of phase 1 and 2? Does phase 1 mean the solving relaxation, cut separation, and resolving, and phase 2 mean primal heuristics?

    Phase 0 means that the callback has been called in the no relaxation heuristic. Phase 1 means that the callback has been called during the usual B&B tree search. Phase 2 means that the callback has been called during the "IMPROVE" phase triggered by one of the parameters ImproveStartGap, ImproveStartNodes, ImproveStartTime.

    If I add the lazy constraints in the model, not by callback but attribute Lazy. Is it correct to set Lazy=-3? Since the doc says they will be treated as user cuts.

    If you want to add the constraints as lazy constraints then you should use one of the values \(\{1,2,3\}\), otherwise these constraints will be treated as user cuts. If you are setting your lazy constraints via the Lazy attribute, then you should definitely try adding these lazy constraints as normal constraints to your model. This is because when setting the Lazy attribute for a constraint \(c\), \(c\) will be constructed before the optimization starts and added to the lazy constraints pool, i.e., you don't save construction time and Gurobi is not able to use the constraint information in presolve.

    I know that when adding a lazy constraint by cbLazy, gurobi will notify all succeeding nodes of these new added lazy constraints, Is it the same behavior for cuts? Or the cuts are only applied for the descendent/child nodes?

    It's the same behavior, cf. the documentation of the cbCut method.

    For large num and expensive constraints, is there another way to deal with them?

    As mentioned above, usually it is best to add those expensive constraints directly to the model and not treat them as lazy constraints. An alternative would be to think of a different more sparse formulation. If you are working with a specific model class, you should definitely search for alternative formulations in the literature. Maybe there is something out there to improve the density of your complex constraints.

    Is it possible to let independent/concurrent MIP models to communicate with each other?

    Gurobi's Concurrent Optimizer communicates the best found solution between multiple parallel runs. It is not possible to communicate manual information with the Concurrent Optimizer.
    Communication between two MIP models can be achieved when you follow a multiprocessing approach, cf. How do I use multiprocessing in Python with Gurobi? You would have to save relevant information in private objects of the models and exchange the information between the two models in callbacks. Please note that this is not an easy approach so you should definitely evaluate the possible benefits of having two MIPs communicating with each other vs running them in sequence.

    Best regards,
    Jaromił

    0
  • ce jekl
    Collaborator
    Investigator

    Hi, Jaromił

    Thank you for your quick response and patience!

    Adding a constraint as a lazy constraint and as a user cut will not benefit the solution process. Lazy constraints will be sorted out if they are no longer needed and handled just as user cuts would be. If you want to add a subset of your lazy constraints as user cuts, then I would recommend to add them as normal constraint. This way Gurobi's presolve can use this information to probably improve the presolved model.

    Do you mean if a lazy constraint is not needed, it will be used just as cuts automatically in gurobi? That makes adding lazy constraints as user cuts in MIPNODE by cbCut(what I did) meaningless.

    Did you try adding them all to your model? Gurobi can often reduce the density and complexity of constraints in presolve so I think it is definitely worth a try.

    Of course, the first thing I try is to add them all to my model, that's not working, due to the constraint being hard and dense.

    Phase 0 means that the callback has been called in the no relaxation heuristic. Phase 1 means that the callback has been called during the usual B&B tree search. Phase 2 means that the callback has been called during the "IMPROVE" phase triggered by one of the parameters ImproveStartGap, ImproveStartNodes, ImproveStartTime.

    Out of curiosity, Is the "IMPROVE" phase still a B&B tree search? IMO, Setting these parameters only changes the MIPFocus of gurobi.

    It's the same behavior, cf. the documentation of the cbCut method.

    Sorry, I can't find any relevant information about the behavior of cbCut. It remains a question that whether a cut generated in one node can be applied to another node. Since cbCut only supports global cut, it may not be a problem. Will gurobi add local cuts internally?

    As mentioned above, usually it is best to add those expensive constraints directly to the model and not treat them as lazy constraints. An alternative would be to think of a different more sparse formulation. If you are working with a specific model class, you should definitely search for alternative formulations in the literature. Maybe there is something out there to improve the density of your complex constraints.

    Directly adding these expensive constraints to the model is not working, which I have tried many times. I will try to search the literature.

    Gurobi's Concurrent Optimizer communicates the best found solution between multiple parallel runs. It is not possible to communicate manual information with the Concurrent Optimizer.
    Communication between two MIP models can be achieved when you follow a multiprocessing approach, cf. How do I use multiprocessing in Python with Gurobi? You would have to save relevant information in private objects of the models and exchange the information between the two models in callbacks. Please note that this is not an easy approach so you should definitely evaluate the possible benefits of having two MIPs communicating with each other vs running them in sequence.

    Thank you very much!

    Best regards,

    Cero

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Happy New Year Cero,

    Do you mean if a lazy constraint is not needed, it will be used just as cuts automatically in gurobi? That makes adding lazy constraints as user cuts in MIPNODE by cbCut(what I did) meaningless.

    Correct. Lazy constraints are added to the cut pool immediately to cut off the found feasible solution and can be removed or re-added during the optimization process.

    Out of curiosity, Is the "IMPROVE" phase still a B&B tree search? IMO, Setting these parameters only changes the MIPFocus of gurobi.

    Yes, the B&B tree search continues while in the "IMPROVE" phase but with settings shifted towards finding feasible solutions.

    Sorry, I can't find any relevant information about the behavior of cbCut. It remains a question that whether a cut generated in one node can be applied to another node. Since cbCut only supports global cut, it may not be a problem. Will gurobi add local cuts internally?

    From the documentation: "Cutting planes can be added at any node of the branch-and-cut tree. However, they should be added sparingly, since they increase the size of the relaxation model that is solved at each node and can significantly degrade node processing speed." Gurobi does not support local cuts, meaning that every user cut and lazy constraint will/can be used in any other node of the B&B tree.

    Directly adding these expensive constraints to the model is not working, which I have tried many times. I will try to search the literature.

    Interesting, would you like to share the model's statistics without lazy constraints (first 20-30 lines of the log file) or even share the model? Please see Posting to the Community Forum for more information on sharing files in the Community.

    Best regards,
    Jaromił

    0

Please sign in to leave a comment.