Making Bound Consistency as Effective as Arc Consistency

Christian Bessière 1 Thierry Petit 2, 3 Bruno Zanuttini 4
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
4 Equipe MAD - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : We study under what conditions bound consistency (BC) and arc consistency (AC), two forms of propagation used in constraint solvers, are equivalent to each other. We show that they prune exactly the same values when the propagated constraint is connected row convex / closed under median and its complement is row convex. This characterization is exact for binary constraints. Since row convexity depends on the order of the values in the domains, we give polynomial algorithms for computing orders under which BC and AC are equivalent, if any.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00382609
Contributor : Christian Bessiere <>
Submitted on : Friday, February 14, 2014 - 3:18:53 PM
Last modification on : Thursday, February 7, 2019 - 5:46:57 PM
Long-term archiving on: Thursday, May 15, 2014 - 9:40:57 AM

File

bpz09.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00382609, version 1

Citation

Christian Bessière, Thierry Petit, Bruno Zanuttini. Making Bound Consistency as Effective as Arc Consistency. IJCAI'09: 21st International Joint Conference on Artificial Intelligence, Jul 2009, Pasadena, CA, United States. pp.425-430. ⟨lirmm-00382609⟩

Share

Metrics

Record views

573

Files downloads

360