How to get user-defined cut to be applied immediately in MIP solver
AnsweredHi,
I asked a similar question approx. 3 weeks ago but did not get a response, so here is my second attempt. I have implemented a callback in C++ that adds user-defined cuts to the MIP solver (I'm using version 9.0.2). The callback also prints to the standard output (cout) everytime a cut is added, and this was done for debugging purposes. However, as shown below, it appears that the cut is not applied immediately, as the most significant digit of the best lower bound should theoretically jump to 4 after the cut is added, but it only goes to 4 more than two minutes later. According to the following thread:
https://groups.google.com/g/gurobi/c/_JUHVqdNy7s
Gurobi should apply the cut immediately if the solver is run on a single thread, and my implementation is using a single thread. So I am wondering why my user-defined cut is not applied immediately, and if there is a way to ensure that it is? Thank you.
-
Official comment
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 -
Official comment
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?. -
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 -
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 -
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
Post is closed for comments.
Comments
5 comments