Search code examples
scip

SCIP: Children vs Parent vs Siblings

I am implementing a node selector. I was thinking that SCIPgetLeaves will give me the list of current nodes among which one needs to be selected for further branching. After the presolving stage, SCIPgetLeaves in NODESELSELECT() doesn't return any node. Instead, I had to use SCIPgetFocusNode().

The documentation states that the NODESELSELECT() chooses one of leaves, children and siblings, so I tried collecting all three. Is there a reason why children and siblings of the root node are not included in leaves after the presolving stage? Just trying to understand the design of SCIP.

Solution

  • All three node types relate to the focus node:

    • SCIPgetChildren() offers quick access to the children newly created via branching
    • SCIPgetSiblings() offers access to the sibling(s) of the focus node
    • SCIPgetLeaves() is the rest with more distant relationships to the focus node

    Just keep in mind that with every selection, the open nodes are partitioned into the 3 types above.

    The node solution process greatly benefits from the possibility of warm/hotstarting the dual Simplex Algorithm, which is why SCIP (and other solvers as well) mostly perform diving (also called "plunging") down the tree, with some limits. This requires quick access to the children of the focus node.

    Have a look at src/scip/nodesel_dfs.c for a good example of a simple node selection.