Skip to Main content Skip to Navigation
Conference papers

Propagating Conjuctions of ALLDIFFERENT Constraints

Abstract : We study propagation algorithms for the conjunction of two ALLDIFFERENT constraints. Solutions of an ALLDIFFERENT constraint can be seen as perfect matchings on the variable/value bipartite graph. Therefore, we investigate the problem of finding simultaneous bipartite match-ings. We present an extension of the famous Hall theorem which characterizes when simultaneous bipartite matchings exists. Unfortunately, finding such matchings is NP-hard in general. However, we prove a surprising result that finding a simultaneous matching on a convex bipartite graph takes just polynomial time. Based on this theoretical result, we provide the first polynomial time bound consistency algorithm for the conjunction of two ALLDIFFERENT constraints. We identify a pathological problem on which this propagator is exponentially faster compared to existing propagators. Our experiments show that this new propagator can offer significant benefits over existing methods.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00558126
Contributor : Martine Peridier <>
Submitted on : Friday, October 11, 2019 - 11:47:01 AM
Last modification on : Monday, July 20, 2020 - 1:06:06 PM

File

aaai10-overlap.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00558126, version 1

Citation

Christian Bessière, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, Toby Walsh. Propagating Conjuctions of ALLDIFFERENT Constraints. AAAI Conference on Artificial Intelligence, Jul 2010, Atlanta, GA, United States. pp.27-32. ⟨lirmm-00558126⟩

Share

Metrics

Record views

239

Files downloads

19