A Fast Arc Consistency Algorithm for n-ary Constraints

Olivier Lhomme, Jean-Charles RéginAAAI 2005

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.

  1. The "Shavable" Oracle: Rather than testing every value blindly, QuickShaving only tests values that have previously triggered a failure.
  2. 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.
  3. Integration: Implemented as a wrapper around standard search (QS-Search), it maintains a dynamic shavableList updated 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.

Performance comparison on hard NK model problems where standard AC times out.

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.

Overhead comparison on large N-Queens problems showing minimal performance penalty.

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

BibTeX
@inproceedings{lhomme2005fast,
  author = {Olivier Lhomme and Jean-Charles Régin},
  title = {{A Fast Arc Consistency Algorithm for n-ary Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2005},
}
Figure