Decision Optimization

Expand all | Collapse all

Terminal nodes in Branch and Bound

  • 1.  Terminal nodes in Branch and Bound

    Posted Mon September 13, 2021 10:39 AM
    Hello all,

    I am using CPLEX 12.10.0 and I am trying to get the number of terminal nodes in a branch-and-cut tree along with some information of these nodes like a optimal dual solution if it exists. The closest thing I could do is a heuristic callback but it seems like it is called only at nodes that will be branched. Is there a method you could suggest for this problem?

    Thank you in advance.

    Binh Truong Gia

  • 2.  RE: Terminal nodes in Branch and Bound

    Posted Wed September 15, 2021 01:10 AM
    In the C Callable library, you can have:

    int Nodes_Left = CPXgetnodeleftcnt(env, lp); // gives the number of unfathomed nodes if you are terminating the MIP prematurely
    int Ndcnt = CPXgetnodecnt(env, lp); // gives the number of explored nodes on termination

    What do you mean by optimal dual solution in the context of an MIP?

    CPLEX User

  • 3.  RE: Terminal nodes in Branch and Bound

    Posted 28 days ago
    I'm not optimistic that you can do this. When CPLEX creates branches, my impression is that it uses the objective bound at the parent as the initial bound for the children, and tightens them only when (if) it moves to the child node. If parent P is separated into children C1 and C2, after which CPLEX moves elsewhere in the tree (because it is not set to depth first search), and at some other node N and incumbent is found that is better than the bound at P, then I think it will prune C1 and C2 without ever solving the node LPs there (and in a way that you could not intercept in a callback). As far as I know, there is no callback that can be invoked whenever CPLEX wants to prune a node.

    Paul Rubin
    Professor Emeritus
    Michigan State University