Predicting the Size of Depth-First Branch and Bound Search Trees
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 594-599.
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.
@inproceedings{ijcai2013p95,
title = {Predicting the Size of Depth-First Branch and Bound Search Trees},
author = {Lelis, Levi H. S. and Otten, Lars and Dechter, Rina},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {594--599},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/95},
}
TY - CPAPER TI - Predicting the Size of Depth-First Branch and Bound Search Trees AU - Lelis, Levi H. S. AU - Otten, Lars AU - Dechter, Rina T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 594 EP - 599 UR - https://ijcai.org/proceedings/2013/95 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
