Propagating Conjunctions of AllDifferent Constraints

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

Abstract

This paper, originally presented at AAAI 2010, addresses a fundamental challenge in Constraint Programming (CP): the efficient handling of multiple global constraints that share variables. Specifically, it focuses on the conjunction of two AllDifferent constraints. While finding a solution for such overlapping constraints is generally NP-hard, the authors prove that enforcing bound consistency is polynomial-time solvable for ordered domains. They introduce a new propagator that generalizes Hall’s Marriage Theorem, significantly reducing search space and execution time compared to treating constraints independently.

The Challenge of Overlapping Constraints

In constraint satisfaction problems, the AllDifferent constraint ensures that a set of variables all take distinct values. In practice, these constraints often overlap—for instance, in scheduling where different departments share common courses and classrooms. Standard solvers typically treat these as separate entities, propagating information individually and only "communicating" by updating shared variable domains. This local reasoning misses global contradictions that arise from the overlap.

Illustration of overlapping variable sets $A^S$, $A^{ST}$, and $A^T$ across different domains.

Methodology: Generalizing Hall’s Theorem

The authors bridge graph theory and constraint propagation by extending Hall’s Marriage Theorem to a Simultaneous Hall Condition (SIM-HC). This condition characterizes when a simultaneous matching exists for two overlapping sets of variables.

While simultaneous matching is NP-complete for general graphs, the authors demonstrate it is polynomial-time solvable if the variable-value graph is convex. In CP, convexity corresponds to variables having interval domains (e.g., a task must start between 9:00 AM and 12:00 PM), which is common in scheduling. The resulting propagator enforces bound consistency in $O(nd^3)$ time by decomposing the SIM-HC into a set of arithmetic constraints that existing solvers can handle efficiently.

Key Results and Empirical Evaluation

The approach was evaluated using randomly generated problems with varying degrees of overlap and binary ordering relations. The experimental results demonstrate that the "Overlapping Bound Consistency" (OBC) propagator is a significant upgrade over standard methods.

Performance comparison between standard BC, DC, and the proposed oBC propagator.

As shown in the results table, the OBC propagator (labeled oBC) reduced the average number of backtracks from millions (for standard BC) to just 9,561. Furthermore, it solved 285 out of 450 instances within the time limit, compared to only 54 for standard BC and 181 for DC. Even with the overhead of more complex reasoning, OBC proved faster on average because it avoided exploring massive, futile branches of the search tree.

Conclusion and Future Work

The paper demonstrates that simultaneous reasoning about overlapping constraints is fundamentally more powerful than sequential reasoning. The SIM-HC captures "bottlenecks" created by shared values more accurately than independent checks. While the current framework is limited to two AllDifferent constraints and bound consistency, it opens the door for applying "simultaneous matching" logic to other global constraints like NVALUE or SEQUENCE. Future work may focus on lowering the $O(nd^3)$ complexity for larger-scale applications.

Summary updated

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