The bias introduced by the node selection procedure is worth investigating.

[GregorCH]

@pierre-lebodic had the idea to measure distances between leaves, to know whether part of the tree is over/under represented. Can you concretize this further?

[pierre-lebodic]

We could measure distances between nodes as a function of their lowest common ancestor. I'm not sure what would be the best way to use this, however. I think the alternatives we're considering at the moment are simpler, so I suggest we try them first.

[GregorCH]

Thanks for sharing the article, this is an example of a well-written Wikipedia entry, I would say.

I was wondering about a practical application of the distances. Now I see one. What about a node selection that, at each step, maximizes the total distance from all previously seen leaf nodes. Of course, there are some practical caveats to this until this can be implemented into the real search. However, I would expect that using such a selection rule could be beneficial for the tree-size estimation. If this is indeed the case, an implementation of this rule could also be beneficial within SCIP for the real solving process.

[pierre-lebodic]

Happy to help! ^_^

I didn't have node selection in mind, but rather a way to change the way we estimate the size of the tree not yet explored.

Suppose that you encode every node with a bit string. The root is the empty string. To get the bit string of the left (resp. right) child of a node, concat 0 (resp. 1) to the string. We can define the similarity between any two nodes as the height of the lowest common ancestor. This is given by the first different bit in their bit strings.

Now, when estimating the size of the subtree at a given node at the frontier, we can use other samples and change their weights depending on their similarity with the node being estimated.

One reason for choosing the height of the lowest common ancestor rather than the actual distance between two nodes is that it would penalise samples that are deep compared to shallow samples, thus biasing the estimate towards smaller trees.

Regarding the node selection, what makes you think that it would be beneficial for the solving process?

[GregorCH]

@JanMerlinV suggested in one of our discussions that the SCIP node selection rule tends to stay in one subtree for a long time and hence has a negative influence on the estimation. In the exploration-exploitation tradeoff language, it exploits too much.

The suggested node selection would rather explore the search domain. I would be curious if the suggested node selection yields a better estimation, in the first place. If it does, it would be worth investigating the algorithmic consequences in the real solver. This would be one possible direction for an algorithmic enhancement that comes from the estimation.