Skip to main content

Pruning the search tree from Callback

Answered

Comments

2 comments

  • Philip Taffet
    Gurobi-versary
    Conversationalist
    Curious

    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
  • Marco Corrao
    Gurobi-versary
    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.

    Best

    Marco

    0

Please sign in to leave a comment.