Introduction
In constraint programming, the primary challenge is finding variable assignments that satisfy a set of rules efficiently. The standard approach, Arc-Consistency (AC), is highly effective at removing values that cannot be part of a solution but often fails to detect contradictions deep within a search tree. This leads to the exploration of massive, unproductive subtrees. While a stronger technique known as shaving (or Singleton Arc Consistency) exists—where values are tentatively assigned to test for failure—it is typically too computationally expensive for general use.
This paper introduces "Quick Shaving" (QS), a lightweight inference mechanism that provides the pruning power of shaving with the low overhead of standard arc-consistency. By using search failures as an "oracle" to predict which values to test, QS achieves significant speedups on difficult problems while maintaining minimal performance penalties when extra pruning is not possible.
Methodology: The QuickShaving Strategy
QuickShaving employs a "pessimistic" strategy guided by the search process itself to focus its pruning efforts.
- The "Shavable" Oracle: Rather than testing every value blindly, QuickShaving only tests values that have previously triggered a failure.
- Backtrack-Triggered Testing: If an assignment $x=a$ at search depth $k$ leads to an immediate failure, the algorithm marks $x=a$ as "shavable." Upon backtracking to depth $k-1$, the algorithm specifically "shaves" that value.
- Integration: Implemented as a wrapper around standard search (
QS-Search), it maintains a dynamicshavableListupdated as the search identifies dead ends.
Unlike standard shaving, which may repeatedly test consistent values, QuickShaving uses search history to ensure that a value is tested and found consistent at most once per branch, theoretically bounding its overhead.
Experimental Evaluation
The algorithm was evaluated using two distinct benchmarks:
- Random Set of Tuples (NK Model): Used to test hard constraint satisfaction problems near the "phase transition" point where problems are most difficult.
- Classic Puzzles (N-Queens): Used to measure the computational overhead in scenarios where shaving typically provides little to no extra pruning.
Key Results and Discussion
The core insight of QuickShaving is that search failures are high-quality hints for domain pruning. On hard problems, this approach yields exponential gains. As shown in the results for the 50-variable NK model, standard Arc-Consistency often times out (exceeding 600 seconds), whereas QuickShaving solves the same instances in under 0.25 seconds.
Furthermore, the algorithm acts as "low-cost insurance." On problems like N-Queens where shaving is largely ineffective, the overhead remains negligible. For large instances up to $N=100$, execution times for QuickShaving were nearly identical to standard AC, and in some cases, even slightly faster due to better-informed heuristics.
Conclusion
QuickShaving effectively bridges the gap between weak, fast inference (AC) and strong, slow inference (Shaving). While currently optimized for discrete domains, future work could explore its interaction with complex dynamic variable-ordering heuristics and its potential application in continuous constraint environments. The simplicity of its implementation makes it a practical addition to modern constraint solvers.
Summary updated