Pruning the search tree from Callback
AnsweredHi
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 workaround 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 ?

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 bigM constraints and nogood 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} (1y_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 workaround to set locallyvalid 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
Please sign in to leave a comment.
Comments
2 comments