Incremental Breakout Algorithm with Variable Ordering

May 2003

Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2003)

Volume

Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2003)

All Papers

This paper presents the Incremental Breakout Algorithm with Variable Ordering (IncBA). This algorithm belongs to the class of local search algorithms for solving Constraint Satisfaction Problems (CSP), and is based on the standard breakout algorithm extended by an incremental solving scheme combined with variable ordering. By evaluating this algorithm with two large sets of Graph Colouring and Scheduling problems, we show that it outperforms the standard breakout method by requiring 101 -103 less constraint checks for solving under- and mediumconstrained problems. Since the proposed scheme is extremely simple, it can be easily applied to other local search methods. With regards to scheduling problems we show that the algorithm delivers solutions of better quality and thus has optimization properties. In this paper we formalize this algorithm, prove its correctness and describe the execution details in the form of pseudo code. At the end of the paper we summarize the results and draw our conclusions.