A random node selection rule would get a backtrack probabliity p between 0 and 1, and a best-bound frequency f.
It selects a child node with probabilty 1 - p (using the SCIP child prioritization to choose between left and right), and backtracks with with probability p. In the case of a backtrack, the best estimate node is selected in f - 1 out of f cases, and the lower bound defining node in the remaining case.
It might not be possible to obtain the estimates from the vbc output. We may also simply backtrack to the lower bound defining node, or select among all leaf nodes randomly with a probability proportional to its current absolute gap. An example: Node 1 has a current gap (distance from the cutoff bound) of 10, and node 2 has a gap of 5. Then, the random selection would choose node 1 with probability 10/15 and node 2 with probability 5/15.
The downside of this approach is that its runtime is linear in the number of leaf nodes at every backtrack.
This implementation will not influence the behavior of the leaf-based estimators WBE and Ratio, because they only receive a shuffled leaf list. However, this node selection has important consequences for the Cornuejols profile estimator, or the suggested estimator based on the open node frontier.
A random node selection rule would get a backtrack probabliity p between 0 and 1, and a best-bound frequency f. It selects a child node with probabilty 1 - p (using the SCIP child prioritization to choose between left and right), and backtracks with with probability p. In the case of a backtrack, the best estimate node is selected in f - 1 out of f cases, and the lower bound defining node in the remaining case.
It might not be possible to obtain the estimates from the vbc output. We may also simply backtrack to the lower bound defining node, or select among all leaf nodes randomly with a probability proportional to its current absolute gap. An example: Node 1 has a current gap (distance from the cutoff bound) of 10, and node 2 has a gap of 5. Then, the random selection would choose node 1 with probability 10/15 and node 2 with probability 5/15. The downside of this approach is that its runtime is linear in the number of leaf nodes at every backtrack.
This implementation will not influence the behavior of the leaf-based estimators WBE and Ratio, because they only receive a shuffled leaf list. However, this node selection has important consequences for the Cornuejols profile estimator, or the suggested estimator based on the open node frontier.