Making the Breakout Algorithm Complete Using Systematic Search

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