Abstract
Constraint Satisfaction Problems (CSPs) are fundamental to various domains, including scheduling, circuit design, and database configuration. While standard propagation techniques like Arc Consistency (AC) and Generalized Arc Consistency (GAC) are widely used, they often fail to prune the search space effectively in complex scenarios because they process constraints in isolation. This paper presents novel algorithms for strong local consistencies, such as maxRPC3 and maxRPWC+, which leverage constraint intersections and caching mechanisms to improve pruning power without prohibitive computational overhead. Experimental results demonstrate that these methods can achieve speedups of several orders of magnitude over state-of-the-art GAC algorithms, particularly in problems with interleaved table constraints.
Introduction
In the field of Constraint Satisfaction Problems (CSPs), solvers typically employ a combination of exhaustive search and constraint propagation. Propagation acts as a "look-ahead" mechanism, removing values from variable domains that cannot participate in any valid solution. By shrinking the search space early, propagation reduces the total number of nodes the solver must explore.
Currently, the industry standards for propagation are Arc Consistency (AC) for binary constraints and Generalized Arc Consistency (GAC) for non-binary constraints. While these methods are computationally efficient, they are considered "weak" because they only examine one constraint at a time. Stronger consistency levels exist that could theoretically prune much more of the search tree; however, their high computational cost has historically outweighed their benefits. This research bridges that gap by introducing high-performance algorithms that make strong local consistencies practical for real-world applications.
Algorithmic Improvements
The research introduces several key algorithmic advancements designed to reduce the overhead of strong consistency checks across different constraint types.
Binary Constraints: maxRPC3 and maxRPC3rm
For binary constraints, the author developed maxRPC3 and its variant maxRPC3rm. These algorithms improve upon the "max Restricted Path Consistency" (maxRPC) framework. The primary innovation here is the use of residues—cached supports from previous consistency checks. By remembering which values supported a variable in previous iterations, the solver avoids redundant constraint checks, which were the primary source of overhead in earlier maxRPC implementations.
Non-Binary Table Constraints: maxRPWC+
Table constraints, which define allowed combinations of values explicitly, are common in configuration and database problems. The paper introduces maxRPWC+, based on "max Restricted Pairwise Consistency." Unlike standard GAC algorithms that process table constraints in isolation, maxRPWC+ specifically exploits the intersections between constraints. By analyzing how overlapping constraints restrict one another, maxRPWC+ can identify and remove inconsistent tuples that GAC would otherwise miss.
Adaptive Propagation
Recognizing that the optimal level of consistency often depends on the specific problem instance or even the current state of the search, the author implemented adaptive heuristics. These heuristics allow the solver to dynamically switch between different consistency levels (e.g., transitioning between Singleton Arc Consistency (SAC) and maxRPWC) during the search process. This flexibility ensures that the solver applies expensive pruning only when it is likely to yield significant search space reductions.
Evaluation and Results
The proposed algorithms were evaluated using standard benchmark CSP problems and specific problem classes involving interleaved table constraints. The results highlight three major advantages:
- Significant Speedups: The
maxRPWC+algorithm demonstrated performance improvements of several orders of magnitude compared to state-of-the-art GAC algorithms on problems with high degrees of constraint overlap. - Robustness: The adaptive heuristics created a more robust solver. By dynamically adjusting the propagation strength, the solver avoided the performance pitfalls associated with using a single, static propagator across diverse problem types.
- Practical Integration: A key focus of the work was ensuring these algorithms could be easily integrated into existing Constraint Programming (CP) solvers, making the theoretical benefits accessible to practitioners.
Conclusion and Future Work
This research demonstrates that strong local consistencies can be made computationally competitive through intelligent caching and by exploiting constraint intersections. By reducing the CPU overhead traditionally associated with these methods, the author has provided a path for more efficient CSP solving in complex domains.
Future work will focus on integrating maxRPWC+ with the "Simple Tabular Reduction" (STR) family of algorithms, which are currently the fastest known methods for GAC on table constraints. Additionally, the author plans to extend these concepts to Bounds Consistency (BC) for linear constraints and further refine the switching logic within the adaptive propagation heuristics.
Summary updated