Exploring Parameterized Relational Consistency

Consistency properties and algorithms for achieving them are at the heart of the success of Constraint Programming. For non-binary Constraint Satisfaction Problems (CSPs), the relational-consistency property R(i,j)C of [Dechter and van Beek 1997] may add new non-binary constraints to the constraint network, thus modifying its topology. The domain-filtering properties of [Bessiere et al. 2008] filter the domains of the variables and leave the constraints unchanged but are restricted to combinations of two constraints. We restate the property of m-wise consistency [Gyssens 1986; Jegou 1993] as relational (*,m)-consistency, R(*,m)C. R(*,m)C ensures that any tuple in a relation is consistent in every combination of m constraints. The main contributions of this document are the design of an algorithm for enforcing R(∗,m)C and the evaluation of its effectiveness in a search procedure solving CSPs. This document thus establishes the usefulness in practice of higher consistency levels in non-binary CSPs