Second-order consistencies

DOI10.1613/JAIR.3180MaRDI QIDQ3081451zbMATH OpenOpenAlexFDO

Authors Christophe Lecoutre, Stéphane Cardon, Julien Vion

Publication date 8 March 2011

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3872

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: 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.

Recommendations

• Path Consistency by Dual Consistency
• Domain filtering consistencies
• An optimal k-consistency algorithm
• Arc consistency and friends
• scientific article; zbMATH DE number 2080322

Cited in

(8)

• Automatically improving constraint models in Savile Row
• On tree-preserving constraints
• Domain filtering consistencies
• Strong local consistency algorithms for table constraints
• Path Consistency by Dual Consistency
• scientific article; zbMATH DE number 2080336 (Why is no real title available?)
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Second-order consistencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3081451)