---
title: "Making the Breakout Algorithm Complete Using Systematic Search"
authors:
  - "Carlos Eisenberg"
  - "Boi Faltings"
doi: ""
url: "https://ijcai.org/proceedings/2003/203"
pdf: "https://ijcai.org/proceedings/2003/0203.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "1374-1374"
track: ""
keywords:
---

# Making the Breakout Algorithm Complete Using Systematic Search

Carlos Eisenberg, Boi Faltings

*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.