Propagating Conjuctions of ALLDIFFERENT Constraints

Christian Bessiere (1) , George Katsirelos (2) , Nina Narodytska (3) , Claude-Guy Quimper (4) , Toby Walsh (3)

1 COCONUT - Agents, Apprentissage, Contraintes
2 CRIL - Centre de Recherche en Informatique de Lens
3 NICTA - National ICT Australia [Sydney]
4 ULaval - Université Laval [Québec]

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.

Domaines: Intelligence artificielle [cs.AI]

Christian Bessiere, 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⟩