Constraint Composite Graph-Based Weighted CSP Solvers: An Empirical Study

Résumé

The Weighted Constraint Satisfaction Problem (WCSP) is a very expressive framework for optimization problems. The Constraint Composite Graph (CCG) is a graphical representation of a given (Boolean) WCSP that facilitates its reduction to a Minimum Weighted Vertex Cover (MWVC) problem by introducing intelligently chosen auxiliary variables. It also enables kernelization: a maxflow procedure used to fix the optimal values of a subset of the variables before initiating search. In this paper, we present some CCG-based WCSP solvers and compare their performance against toulbar2, a state-of-the-art WCSP solver, on a variety of benchmark instances. We also study the effectiveness of kernelization.