Projects per year
Abstract
The ALLDIFFERENT constraint was one of the first global constraints [17] and it enforces the conjunction of one binary constraint, the notequal constraint, for every pair of variables. By looking at the set of all pairwise notequal relations at the same time, AllDifferent offers greater filtering power. The natural question arises whether we can generally leverage the knowledge that sets of pairs of variables all share the same relation. This paper studies exactly this question. We study in particular special constraint graphs like cliques, complete bipartite graphs, and directed acyclic graphs, whereby we always assume that the same constraint is enforced on all edges in the graph. In particular, we study whether there exists a tractable GAC propagator for these global SameRelation constraints and show that AllDifferent is a huge exception: most SameRelation Constraints pose NPhard filtering problems. We present algorithms, based on AC4 and AC6, for one family of SameRelation Constraints, which do not achieve GAC propagation but outperform propagating each constraint individually in both theory and practice.
Original language  English 

Title of host publication  Principles and Practice of Constraint Programming  CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 2024, 2009: Proceedings 
Editors  I. P. Gent 
Publisher  Springer 
Pages  470485 
Number of pages  16 
ISBN (Print)  9783642042430 
DOIs  
Publication status  Published  2009 
Publication series
Name  Lecture Notes in Computer Science 

Volume  5732 
ISSN (Print)  03029743 
Keywords
 ARC
Fingerprint
Dive into the research topics of 'SameRelation Constraints'. Together they form a unique fingerprint.Projects
 1 Finished

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A., Gent, I. P., Leonhardt, U., Mackenzie, A., Miguel, I. J., Quick, M. & Ruskuc, N.
1/09/05 → 31/08/10
Project: Standard