A binary constraint satisfaction problem (BCSP) consist in determining an assignment of values to variables which is compatible with a set of constraints. The problem is called binary because the constraints involve only pairs of variables. The BCSP is a cornerstone problem in Constraint Programming (CP), appearing in a very wide range of real-world applications. In this work, we develop a new exact algorithm which effectively solves the BCSP by reformulating it as a k-clique problem on the underlying microstructure graph representation. Our new algorithm exploits the cutting-edge branching scheme of the state-of- the-art maximum clique algorithms combined with two filtering phases in which the domains of the variables are reduced. Our filtering phases are based on coloring techniques and on heuristically solving an associated boolean satisfiability (SAT) problem. In addition, the algorithm initialization phase performs a reordering of the microstructure graph vertices which produces an often easier reformulation to solve. We carry out an extensive computational campaign on a benchmark of almost 2000 instances which encompasses numerous real and synthetic problems from the literature. The performance of the new algorithm is compared against two SAT-based solvers and three general purpose CP solvers. Our tests reveal that the new algorithm significantly outperforms all the others in several classes of BCSP instances.
Article
View A new branch-and-filter exact algorithm for binary constraint satisfaction problems