Estimating the size of search trees by sampling with domain knowledge

Estimating the size of search trees by sampling with domain knowledge

Gleb Belov, Samuel Esler, Dylan Fernando, Pierre Le Bodic, George L. Nemhauser

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 473-479. https://doi.org/10.24963/ijcai.2017/67

We show how recently-defined abstract models of the Branch-and-Bound algorithm can be used to obtain information on how the nodes are distributed in B&B search trees. This can be directly exploited in the form of probabilities in a sampling algorithm given by Knuth that estimates the size of a search tree. This method reduces the offline estimation error by a factor of two on search trees from Mixed-Integer Programming instances.
Keywords:
Combinatorial & Heuristic Search: Combinatorial search/optimisation
Constraints and Satisfiability: Solvers and Tools