Second-Order Consistencies

作者：Lecoutre Christophe^*; Cardon Stephane; Vion Julien

来源：Journal of Artificial Intelligence Research, 2011, 40: 175-219.

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. I

• 出版日期2011