Propagating Conjunctions of AllDifferent Constraints

Christian Bessiere, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, Toby Walsh

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.
BibTeX
@inproceedings{bessiere2010propagating,
  author = {Christian Bessiere and George Katsirelos and Nina Narodytska and Claude-Guy Quimper and Toby Walsh},
  title = {{Propagating Conjunctions of AllDifferent Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7554},
}
Figure