implement cutting plane algorithm

Answered

Comments

4 comments

  • Miranda

    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
    Comment actions Permalink
  • Matthias Miltenberger

    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
    Comment actions Permalink
  • Miranda

    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
    Comment actions Permalink
  • Matthias Miltenberger

    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
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk