Adaptive Neighborhood Inverse Consistence as Lookahead for Non-Binary CSPs

Contributions 1.The property Relational Neighborhood Inverse Consistency (RNIC) 2.Characterization of RNIC in relation to previously known properties3.An efficient algorithm for enforcing RNIC, bounded by degree of the dual graph 4.Three reformulations of the dual graph to address topological limitations of the dual graph 5.An adaptive, automatic selection policy for choosing the appropriate dual graph 6.Empirical evidence on difficult CSP benchmarks Definition A Constraint Satisfaction Problem (CSP) is a combinatorial decision problem defined by a set of variables {A,B,C,…}, a set of domain values for these variables, and a set of constraints {R1,R2,R3,…} restricting the allowable combinations of values for variables. The task is to find a solution (i.e., an assignment of a value to each variable satisfying all constraints), or to find all such solutions. Local Consistency Local consistency is at the heart of Constraint Processing. It guarantees that all values (or tuples) participate in at least one solution in a given combination of variables (or constraints). Neighborhood Inverse Consistency (NIC) ensures that every value in the domain of a variable can be extended to a solution in the sub-problem induced by the variable and its neighborhood [1]