Search Strategies for an Anytime Usage of the Branch and Prune Algorithm
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 468-472.
Abstract
When applied to numerical CSPs, the branch and prune algorithm (BPA) computes a sharp covering of the solution set. The BPA is therefore impractical when the solution set is large, typically when it has a dimension larger than four or five which is often met in underconstrained problems. The purpose of this paper is to present a new search tree exploration strategy for BPA that hybridizes depth-first and breadth-first searches. This search strategy allows the BPA discovering potential solutions in different areas of the search space in early stages of the exploration, hence allowing an anytime usage of the BPA. The merits of the proposed search strategy are experimentally evaluated.Raphaël Chenouard, Alexandre Goldsztejn, Christophe Jermann
@inproceedings{ijcai2009p85,
title = {Search Strategies for an Anytime Usage of the Branch and Prune Algorithm},
author = {Chenouard, Raphaël and Goldsztejn, Alexandre and Jermann, Christophe},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {468--472},
year = {2009},
url = {https://ijcai.org/proceedings/2009/85},
}
TY - CPAPER TI - Search Strategies for an Anytime Usage of the Branch and Prune Algorithm AU - Chenouard, Raphaël AU - Goldsztejn, Alexandre AU - Jermann, Christophe T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 468 EP - 472 UR - https://ijcai.org/proceedings/2009/85 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
