MARS: a hybrid scheme based on Resolution Search and Constraint Programming for Constraint Satisfaction Problems

19 pagesIn this paper, we present a solution approach based on Chv\'{a}tal's Resolution Search [Chvatal 1997] to solve combinatorial optimization problems. Resolution Search constitutes an alternative to classical enumeration methods and possesses strong connections to nogood recording approaches, and in particular dynamic backtracking, though it is designed to deal with binary linear programming problems. Accordingly, we suggest to hybridize the procedure using constraint programming techniques, in order to apply it to Constraint Satisfaction Problems (CSP). Furthermore, the introduction of such techniques allows some specific improvements that speed up the process and let many outcomes for further research. In order to evaluate the interest of the proposed method, we use it to tackle some particular graph coloring instances, known as the Queens_n2 problem. The experimental results obtained so far prove the validity of the approach and compete with state-of-the-art complete solution methods