How to get user-defined cut to be applied immediately in MIP solver

Answered

Comments

4 comments

  • Official comment
    Matthias Miltenberger

    Hi!

    Please excuse us for not responding to your first post.

    Did you follow the instructions about adding cuts? Could you please also share the final statistics of the optimization run? There should be a section about added cuts and this should also show your user cuts. To me, this looks like your cuts have not been added properly.

    Cheers,
    Matthias

    Comment actions Permalink
  • Mohd. Hafiz Hasan

    Hi Matthias,

    Thanks for the prompt response. 

    1. My implementation does set the PreCrush parameter to 1, and also only adds cuts when where == GRB_CB_MIPNODE. What convinces me that my implementation is adding the cuts correctly is that the cuts are applied immediately by the MIP solver when they are discovered at the root node, as shown below. The problem only occurs when cuts are added deep into the tree.

     

    2. Here are the final statistics of the optimization run:

    Thanks again.

     

    0
    Comment actions Permalink
  • Mohd. Hafiz Hasan

    Hi,

    It seems like I misunderstood the output of the log in the context of how branch-and-bound generally works earlier, and as a result I was focusing my attention on the wrong column of the output log. I should have looked at the current node column instead of the best bound, and the current node column clearly shows that the cut is applied immediately, as reflected by the immediate jump in the most significant digit of the node relaxation objective value.

    It appears that the solver needs to expand all the leaf nodes before the effect of the cut is reflected in the best bound, and it takes longer for this to happen the more unexplored nodes there are at the time the cut is introduced (which explains why the best bound improved immediately close to the root node but not deeper into the tree).

    So now, I'm wondering if, aside from the MIPFocus parameter, there is another parameter exposed to the end user to have the solver expand the unexplored nodes as quickly as possible (or perhaps do something else) to have the effect of the cut be reflected in the best bound as soon as possible? Or would I be better off just aborting the solver, adding the cut, and then resuming it to have the best bound immediately reflect the cut?

    0
    Comment actions Permalink
  • Sonja Mars

    Hi,

    From what I see, it seems your cut was added correctly and registered into Gurobi. However, please note a few things: The cut is not added right away it has to wait for the next sync point, when you are already in the Branch-and-Bound tree. In the root node this is different. Then the cut is applied more or less right away and also reflects in a change in the global lower bound ("BestBd" in the log). However, if you add user cuts in the tree search, we don't take them for changing the global lower bound immediately, because we already have open nodes (and these nodes have already been generated). We would have to touch every open node and change the bound there or recompute the root node to make this change happen. 

    Hope this explains it a bit.

    Stopping the solver, adding the cut and checking out performance sounds like a good idea to test. You can also try to run our automated tuning tool to find some good parameters. 

    Best,

      Sonja

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk