Second-Order Consistencies
  In this paper, we propose a comprehensive study of second-order consistencies
(i.e., consistencies identifying inconsistent pairs of values) for constraint
satisfaction. We build a full picture of the relationships existing between
four basic second-order consistencies, namely path consistency (PC),
3-consistency (3C), dual consistency (DC) and 2-singleton arc consistency
(2SAC), as well as their conservative and strong variants. Interestingly, dual
consistency is an original property that can be established by using the
outcome of the enforcement of generalized arc consistency (GAC), which makes it
rather easy to obtain since constraint solvers typically maintain GAC during
search. On binary constraint networks, DC is equivalent to PC, but its
restriction to existing constraints, called conservative dual consistency
(CDC), is strictly stronger than traditional conservative consistencies derived
from path consistency, namely partial path consistency (PPC) and conservative
path consistency (CPC). After introducing a general algorithm to enforce strong
(C)DC, we present the results of an experimentation over a wide range of
benchmarks that demonstrate the interest of (conservative) dual consistency. In
particular, we show that enforcing (C)DC before search clearly improves the
performance of MAC (the algorithm that maintains GAC during search) on several
binary and non-binary structured problems.
