Pruning the search tree from Callback
Answered
Hi
I have a MILP that include a number of binary variables \(y_i, i \in I\).
Further, my MILP has the property that, if I fix a subset of my binary variables \(y_j, j \in J \subset I \), then there is only a unique integer feasible solution for all the other \(y_k, k \not\in J\) , which I can compute through a separate algorithm.
In order to speed up the solution of my MILP, I therefore plan to use callbacks at each MIPNode as follow:
At every MIPNode callback:
if all variables in the subset J are integral:
1. compute the only feasible solution for the other variables through an external code
2. set the solution with model.cbSetSolution()
3. Use solution with model.cbUseSolution()
However, I already know that this is the only integer solution that can be found going down this node, so I wouldn't want to waste time by further exploring the search down this node.
Hence, I was wondering whether Gurobi 9.1.2 offers any way to manually force pruning of a node after setting my solution or, alternatively, whether there is any work-around that would achieve the same result.
Thanks a lot in advance
Best
Marco
P.S. Since I my model has binary variables which I don't ever want to branch (i.e. all the \(y_k, k \not\in J\), I thought about the possibilty of treating them as continous variables, but this would result in certain MIP relaxations to be seen as feasible and potentially produce a new incumbent solution, which clearly I don't want. Is there a way to force gurobi to discard an integer feasible solution from callback ?
-
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?. -
Here's an idea for a workaround:
I'm assuming your problem is `min(obj)` where `obj` is a variable. You can use a combination of big-M constraints and no-good cuts to form a user cutting plane.
Suppose all of the variables `y_j` where `j\in J` are integral. Let `y'_j` be the value at the current solution. After you compute `y_k` for `k\notin J` and get the objective value `o'` from `\text{cbUseSolution}`, add a cutting plane with `\text{model.cbCut}` of the form
$$M \left( \sum_{j\in J \text{ where } y'_j=0} y_j + \sum_{j \in J \text{ where } y'_j = 1} (1-y_j) \right) + obj \ge o'$$
where `M` is a big enough constant. For any child of the current MIP node, this cut reduces to `obj \ge o'`, which immediately forces the value of the node up to `o'`. Since you have a feasible solution with objective `o'` as well, this should prevent Gurobi from exploring any children of the current node.
In other parts of the tree, the cut reduces to `M+obj \ge o'`. If `M` is sufficiently large, this should be easily satisfied. This also shows that e.g. if you know `obj \ge 0`, then you can pick `M=o'`, so it doesn't have to be too large.
I'm not sure how big `J` is, but you might be disappointed with the frequency with which all the variables in `J` are integral.
0 -
Hi! Thanks a lot for the reply! I implemented it and it seems to be working. Indeed, the approach can also be used as a work-around to set locally-valid cuts from callbacks. It is still unfortunate, however, that one has to burden the problem with new constraints every time a node is to be pruned. Perhaps in the next releases Gurobi could benefit from higher degree of control over the tree search from callbacks, like CPLEX does.
Best
Marco
0 -
Hi Marco and Philip,
I have a stupid question. How can you determine the set of J? The variables with integral value in MIPNODE (LP solution) don't immediately become a fixed variable in the subtree, right?
Best
Cero0
Post is closed for comments.
Comments
4 comments