Skip to Main content Skip to Navigation
Conference papers

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
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes 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, May 14, 2020 - 6:58:06 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

597

Files downloads

371