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 metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Martine Peridier <>
Submitted on : Friday, October 11, 2019 - 11:47:01 AM
Last modification on : Monday, January 11, 2021 - 5:24:09 PM


Publisher files allowed on an open archive


  • HAL Id : lirmm-00558126, version 1


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⟩



Record views


Files downloads