Skip to main content

Adding lazy cuts when a feasible solution is found by branching (indicated by * in logfile)

Answered
Manish Bansal
  • Gurobi-versary
  • First Comment
  • First Question

How can I generate lazy cuts whenever a new feasible solution has been found by branching (indicated by character * at the beginning of an output line of logfile)? I am using MIPSOL and MIPNODE to generate lazy cuts whenever an integral solution is found in the branch-and-bound tree. The code is working except for the "feasible solution found by branching". Am I missing something? I will appreciate your help/guidance.  

Related to

0

Comments

6 comments

Date Votes
  • Jaromił Najman
    • Gurobi Staff
    Edited

    Unfortunately, this is currently not possible.

    Currently, the only way to extract the information about whether a solution has been found by branching or not is by parsing the log messages. You could do that via the MESSAGE callback. Note that it is possible that you get into the MIPSOL callback (multiple times) before the message is printed. Thus, you would have to save the solution information, wait for the MESSAGE callback and check the first character of the string for '*' or 'H'. This however destroys the purpose of your lazy constraints which should have been added when the solution has been found.

    Could you briefly explain why you would like to handle a solution found by branching differently than any other solution found by a heuristic?

    0
  • Manish Bansal
    • Gurobi-versary
    • First Comment
    • First Question

    Hi Jaromil, 

    Thank you for the quick response. Actually, I do not want to handle a solution found by branching differently than any other feasible/integral solution. I want to simply add lazy cuts whenever a feasible solution is found. For the same, I started using MIPSOL callback which is adding cuts correctly, except whenever a solution is found by branching. Is it possible that the MIPSOL callback is not called when a solution is found by branching? 

    FYI. I am also using MIPNODE to detect integral solutions that are not detected by MIPSOL because of minor numerical discrepancy. Even this is not called when a solution is found by branching.  

    0
  • Jaromił Najman
    • Gurobi Staff

    Hi Manish,

    Is it possible that the MIPSOL callback is not called when a solution is found by branching? 

    Any incumbent solution is provided through the MIPSOL callback (note that an incumbent is a new best solution, not any feasible solution). It is irrelevant whether the incumbent has been found by a heuristic or by branching. Do you have any indication that an incumbent is found through branching and is not provided in the MIPSOL callback?

    FYI. I am also using MIPNODE to detect integral solutions that are not detected by MIPSOL because of minor numerical discrepancy. Even this is not called when a solution is found by branching.  

    I don't understand this argument. If the solution is not an incumbent or is not integral, then it will not be provided in a MIPSOL callback. Could you clarify what exactly you mean by "Even this is not called when a solution is found by branching."?

    Best regards, 
    Jaromił

    0
  • Manish Bansal
    • Gurobi-versary
    • First Comment
    • First Question

    Actually my lazy cut was supposed to cut the solution found by branching, which was not happening. That is why I asked "Is it possible that the MIPSOL callback is not called when a solution is found by branching?". However, now I have found that the issue was a minor numerical error in my code. It has now been fixed and everything is working. 

    This implies that an incumbent found through branching is also provided in the MIPSOL callback. 

    Thank you very much for your input. 

    0
  • OneCable OneCable
    • Gurobi-versary
    • Curious
    • Conversationalist

    Hi Jaromil:

    Do you have any indication that an incumbent is found through branching and is not provided in the MIPSOL callback?

    My usual understanding of a lazy constraint is also that it should be called only via MIPSOL callback. However, I am confused by the following paragraphs in official docs (https://docs.gurobi.com/projects/optimizer/en/current/reference/c/callback.html#c.GRBcblazy) :

    You would typically add a lazy constraint by first querying the current node solution (by calling GRBcbget from a GRB_CB_MIPSOL or GRB_CB_MIPNODE callback, using what=GRB_CB_MIPSOL_SOL or what=GRB_CB_MIPNODE_REL), and then calling GRBcblazy() to add a constraint that cuts off the solution. Gurobi guarantees that you will have the opportunity to cut off any solutions that would otherwise be considered feasible.

    MIP solutions may be generated outside of a MIP node. Such solutions do not cause a callback invocation with where equal to GRB_CB_MIPNODE. If you want to have the opportunity to reject all solutions, you must check them when where is equal to either GRB_CB_MIPSOL or GRB_CB_MIPNODE

    The documents seem to indicate that there could be occasions where a lazy constraint is needed to be added in MIPNODE. When would one need to add a lazy constraint in an MIPNODE?

    Even the official code, tsp_c.c, does not cover the case where an MIPNODE needs to be checked and only considers MIPSOL. https://docs.gurobi.com/projects/examples/en/current/examples/c/tsp_c.html

    Thanks

    0
  • Jaromił Najman
    • Gurobi Staff

    Hi OneCable,

    When would one need to add a lazy constraint in an MIPNODE?

    There are specific concepts for Bender's decomposition, which use the root relaxation solution to generate cuts. One example is described in Implementing Automatic Benders Decomposition in a Modern MIP Solver, Bonami et al. 2019

    Best regards, 
    Jaromił

    1

Please sign in to leave a comment.

Didn't find what you were looking for?

New post