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.
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.
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