Predicting the Size of Depth-First Branch and Bound Search Trees
Lists
Only you see this
Abstract
This paper provides algorithms for predicting the size of the Expanded Search Tree (EST) of Depth-first Branch and Bound algorithms (DFBnB) for optimization tasks. The prediction algorithm is implemented and evaluated in the context of solving combinatorial optimization problems over graphical models such as Bayesian and Markov networks. Our methods extend to DFBnB the approaches provided by Knuth-Chen schemes that were designed and applied for predicting the EST size of backtracking search algorithms. Our empirical results demonstrate good predictions which are superior to competing schemes.
BibTeX
@inproceedings{lelis2013predicting,
author = {Levi H. S. Lelis and Lars Otten and Rina Dechter},
title = {{Predicting the Size of Depth-First Branch and Bound Search Trees}},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2013},
url = {https://openreview.net/forum?id=r1EW2mfuWH},
}Loading related content...