Abstract
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
