Skip to main content

Pruning the search tree from Callback




  • Philip Taffet

    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.


  • Marco Corrao
    First Comment
    First Question

    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.




Please sign in to leave a comment.