Making the Breakout Algorithm Complete Using Systematic Search
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 1374-1374.
Abstract
Local search algorithms have been very successful for solving constraint satisfaction problems (CSP). However, a major weakness has been that local search is unable to detect unsolvability and is thus not suitable for tightly and overconstrained problems. We present a hybrid solving scheme where we combine a local search algorithm - the breakout algorithm, with a systematic search algorithm - backtracking. The breakout algorithm is used for identifying hard or unsolvable subproblems and the backtracking algorithm proves the solvability of these subproblems. The resulting hybrid algorithm is complete and is tested on randomly generated graph 3-colouring problems. The algorithm performs extremely well for all areas of the phase transition and outperforms the individual methods by several orders of magnitude.
@inproceedings{ijcai2003p203,
title = {Making the Breakout Algorithm Complete Using Systematic Search},
author = {Eisenberg, Carlos and Faltings, Boi},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {1374--1374},
year = {2003},
url = {https://ijcai.org/proceedings/2003/203},
}
TY - CPAPER TI - Making the Breakout Algorithm Complete Using Systematic Search AU - Eisenberg, Carlos AU - Faltings, Boi T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 1374 EP - 1374 UR - https://ijcai.org/proceedings/2003/203 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
