Is there a way to tell gurobi to stay at root node until a certain condition is met?
AnsweredI'm working on a MIP problem (minimization). Currently, I have an exponentially large family of constraints \(C\), which I separate dynamically by solving an auxiliary problem \(SP\) (for separation problem). \(MP\) refers to the main problem.
The output of \(SP\) provides me with information about which constraint of \(C\) is being violated in the current point (Integer or fractional) for the \(MP\).
I solve \(SP\) for the relaxation, as well as any integer solution.
In node relaxation, I check every new best bound found and, if \(SP\) finds a violated \(C\) then that point is to be cut since, it is proven that, with the current variables values, it would be infeasible in \(MP\) even when considering the relaxation of the integrality conditions.
My issue comes when I check the root relaxation, specifically the best bound obtained while still at the root node.
I would think that, by following the same logic as before, the best bound obtained when the model leaves the root node should be "feasible-ish" for \(MP\) i.e. in the last best bound found in the root node, \(SP\) does not find any \(C\) violated. But that doesn't happen.
The last best bound found before starting branching is not always feasible-ish for \(MP\) I realized this by retrieving the var. values and manually solving \(SP\) with them, finding that there is, at least, one \(C\) violated.
What makes the model decide to leave the root node considering that \(SP\) still finds violated conditions for that last best bound? Why doesn't it try to find a new bound (while still in the root) that doesn't violate \(C\)? Is there a way to stay at the root until reaching a bound for which no cuts are violated?
I think having the model leave the root node with a bound that doesn't violate any additional \(C\) constraints could be benefitial for branching and could have a noticeable impact in the computing times.
-
-
Gurobi Staff
Hi Nicolas,
It is currently not possible to force Gurobi to stay in the root node for a longer amount of time.
What makes the model decide to leave the root node considering that still finds violated conditions for that last best bound? Why doesn't it try to find a new bound (while still in the root) that doesn't violate ? Is there a way to stay at the root until reaching a bound for which no cuts are violated?
There are multiple reasons to leave the root node. Gurobi considers the improvement of the best bound, the improvement of the feasible point, the time spent in the root node so far, number of violations introduced by new cuts and more. These conditions are set in such a way that they work well for many different model classes. Thus, it is possible that for your particular model, the root node is left too early. You could try increasing the time spent on cuts via the Cuts parameter. Maybe, this is already enough to improve the behavior in this case.
Since, you compute your \(SP\), could you use this information to add a cut yourself through a callback? This might solve your issue.
Best regards,
Jaromił0 -
-
Since, you compute your \(SP\) , could you use this information to add a cut yourself through a callback?
Exactly, that's how I'm adding these cuts. First I get the relaxed var. values. With those, I then call \(SP\) and check the output. If I found \(C\) violated then I add the corresponding cut. A simplification is something like this:
def callback(m,where):
if where == GRB.MIPNODE and m.cbGet(GRB.Callback.MIPNODE_STATUS) == 2:
rel_vars = m.cbGetNodeRel(m._vars)
condition_violated, expression = SP(rel_vars)
if condition_violated:
m.cbCut(expression)Is this what you mean?
You could try increasing the time spent on cuts via the Cuts parameter.
I'm currently working with Gurobi cuts, as well as heuristics, turned off since I'm benchmarking the current formulation and separation methods for my model, effectively, when I turn the cuts, then the model stays longer at the root node and I get a better bound.
Thanks!
Thanks!
0 -
-
-
Hi Nicolas,
Is this what you mean?
Yes, that's exactly what I meant.
I'm currently working with Gurobi cuts, as well as heuristics, turned off since I'm benchmarking the current formulation and separation methods for my model, effectively, when I turn the cuts, then the model stays longer at the root node and I get a better bound.
Sounds like you were able to achieve what you wanted at least to some extent.
Is there still something unclear?
Best regards,
Jaromił0 -
-
Hey Jaromil,
If I understood correctly. For the last best bound found there may or may not be violated \(C\) conditions when solving \(SP\). If there aren't any then I'm "lucky" and the best lower bound is feasible for the relaxed model. If I do find a \(C\) condition violated for that bound, but Gurobi decides to leave the root node anyways, then I'm unlucky and the best bound found before leaving the root is not feasible for the relaxed model. Then that makes me believe that Gurobi ""doesn't seem to care"" about that feasibility condition ( the one that must be checked with the \(SP\)) or else it would stay in the root until finding a bound for which there aren't any \(C\) violated.
Thanks in advance!
0 -
-
-
Hi Nicolas,
Your understanding is correct.
What you could try is to run the model as you do right now but save all lazy constraints/user cuts that you added. Then, if after the root node there still is a violated condition of yours, you can terminate the optimization from within the callback. After termination, you then add all the constraints you saved during callback calls and optimize again starting with all the new constraints.
Hope this helps.
Best regards,
Jaromił0 -
-
Got it, I will try that
Thank you very much!
0 -
Please sign in to leave a comment.
Comments
6 comments