Skip to main content

implement cutting plane algorithm

Answered

Comments

5 comments

  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Miranda
    Gurobi-versary
    Investigator
    First Comment

    Followup: I am guessing that I could model my original MIP problem in Gurobi and then use callback function to add my cuts during Gurobi's branch and bound process. Am I right?

    However, in my callback function (used to add cuts). The 'where' value is not equal to GRB.callback.MIPNODE, so that I could not add any cuts. Is there any way to fix this issue? 

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Miranda,

    In general, implementing a cutting plane approach like that is likely to fail sooner or later. It is important to "clean up" your cutting planes to avoid an ever-growing LP. Even then, it can be very hard to solve the problem just by cutting planes. This is the reason every MIP solver uses cutting planes in addition to the branch-and-bound technique.

    To get your custom cutting planes into Gurobi via callbacks, you need to collect the cutting plane data in your callback and then add it using the appropriate callback 'where' state. Please check the callback.py example for more information on how to implement different callback states.

    Cheers,
    Matthias

    0
  • Miranda
    Gurobi-versary
    Investigator
    First Comment

    Hello Matthias,

    Thank you for your quick response. I am currently model my problem as MIP and use callback function to add cuts. In my callback function, I set if where == GRB.Callback.MIPSOL, and meet 'some conditions', then add cbLazy(). I am not very clear of the difference between cbcut() and cbLazy(). In my circumstance, which one is better? 

    I tried cbcut(), but since my 'where' value is not equal to GRB.callback.MIPNODE, I failed to add the cbcut(). Do you know the reason why 'where' != GRB.callback.MIPNODE? 

    Furthermore, by using cbLazy, I got the following output, is 1+7+4 the total number of cuts added? and 1.2s is the total running time? 

    Thank you.

    0
  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Miranda,

    This guide explains the differences between Lazy Constraints and User Cuts quite well:

    What is the difference between user cuts and lazy constraints? – Gurobi Support Portal

    Since lazy constraints are not cuts per se, the total number of cuts in your example is just 8 but using 4 additional lazy constraints.

    To add a cut that was generated in a MIPSOL callback, you need to store the cut in a custom Model data structure, like \(\texttt{model._mycuts}\) and then add them when the solver reaches a MIPNODE callback.

    Cheers,
    Matthias

    0

Post is closed for comments.