TL;DR
This paper introduces a new, faster algorithm for "bounds consistency" propagation of the alldifferent constraint in constraint programming. While achieving the same theoretical worst-case performance as prior methods, their practical implementation significantly outperforms existing algorithms and even commercial solvers on various benchmark problems.
What Problem Does This Paper Address?
Constraint programming (CP) is a powerful technique for solving complex problems by defining variables and constraints on their values. A common approach to solving CP problems involves interleaving search (like backtracking) with constraint propagation. Constraint propagation's role is to reduce the search space by eliminating values from variable domains that cannot lead to a valid solution.
The alldifferent constraint, which requires all variables in a set to take distinct values, is fundamental and widely used in CP. Efficiently propagating this constraint is crucial for overall performance. While various propagation algorithms exist, ranging in their "strength" of consistency (e.g., domain, range, bounds), this paper focuses on improving bounds consistency for alldifferent. Bounds consistency ensures that the minimum and maximum possible values for each variable have a valid "support" within the constraint. Prior work had developed O(n log n) algorithms for this, but the authors aimed for a practically faster solution.
Methods
The paper presents a new algorithm for bounds consistency propagation of the alldifferent constraint. It builds upon the concept of "Hall intervals" and the idea of maintaining "capacities" related to available values. The core innovation lies in a more efficient way of managing these capacities.
Instead of the O(n log n) approach of Puget [1998] which uses a balanced binary tree for counters, this algorithm utilizes a linked list data structure to track "critical capacities." This structure allows for faster updates and testing for zero or negative capacities, which signal the presence of Hall intervals or inconsistencies. The algorithm leverages "path compression" techniques, similar to those used in disjoint set union data structures, to achieve its efficiency. While the theoretical worst-case complexity remains O(n log n) (or even O(n) with advanced data structures), the practical implementation is significantly faster due to reduced overhead.
Datasets
The paper evaluates its algorithm on several types of problems:
- Benchmark Problems:
- "Pathological problems" designed to test worst-case behavior.
- Golomb ruler problems.
- Instruction scheduling problems (from SPEC95 and SPEC2000 benchmarks).
- Random Problems:
- Pure random problems with full domains.
- Random problems with "holes" in the domains (values removed with a certain probability).
- Other Problems:
- n-queens, quasigroup existence, and sport league scheduling problems.
Key Insights and Ideas
- Practical Speedup is Key: While theoretical worst-case complexity is important, the paper demonstrates that a simpler, more efficient data structure can lead to substantial practical performance gains, even when the theoretical complexity is the same.
- The Power of Efficient Data Structures: The choice of data structure for managing capacities (linked list with path compression vs. balanced binary tree) is critical for achieving speedups in constraint propagation.
- Bounds Consistency Sufficiency: For certain problem classes (e.g., those without "holes" in domains), bounds consistency can be as effective as stronger forms of local consistency, making faster bounds consistency propagators highly valuable.
- Identifying Problem Structure: The presence or absence of "holes" in variable domains is a significant factor in determining the best propagation strategy. This suggests potential for adaptive CP solvers.
Key Results
- The proposed algorithm is approximately 2 times faster than the best previous bounds consistency algorithm (Mehlhorn and Thiel's MT) on "Pathological problems."
- It is about 5 times faster than Puget's algorithm (using RC as a calibration point) on the same problems.
- On Golomb ruler problems, the algorithm is 1.6 times faster than the next best propagator and 1.5 times faster than Puget's algorithm.
- On instruction scheduling problems, it also offers a clear performance improvement.
- For random problems with full domains, the algorithm exhibits nearly linear incremental behavior, outperforming quadratic behavior of RC and DC propagators.
- The algorithm significantly outperforms state-of-the-art commercial implementations of stronger forms of local consistency on problems where bounds consistency is sufficient.
Limitations and Future Work
- Theoretical vs. Practical: While the algorithm has the same worst-case theoretical complexity as prior O(n log n) algorithms, the paper notes that further theoretical improvements to O(n) are possible using advanced data structures (interval union-find), though their practical implementation might not always outperform the O(n log n) version.
- Adaptive Solvers: The authors suggest that the ability to identify problem characteristics (like the presence of domain holes) could lead to automatically selecting the best propagator, rather than relying on the modeler. This points towards future work in developing more adaptive constraint solvers.
- Further Benchmarking: The paper mentions a longer version with additional experimentation, implying that more extensive testing could reveal further nuances of the algorithm's performance.
Summary updated