Arc Consistency during Search

Chavalit Likitvivatanavong, Yuanlin Zhang, Scott Shannon, James Bowen, Eugene C. FreuderIJCAI 2007

Abstract

Constraint Satisfaction Problems (CSPs) are central to many AI applications, typically solved using a combination of backtracking search and Arc Consistency (AC) filtering. Traditionally, AC algorithms are designed as standalone components. This paper introduces a specialized framework, Arc Consistency during Search (ACS), which exploits the incremental nature of search by reusing "residual data"—information preserved across search steps. We demonstrate that algorithms like ACS-residue, which avoid costly state restoration during backtracking, significantly outperform theoretically optimal but more complex alternatives in real-world scenarios.

At the heart of many automated reasoning tasks lies the Constraint Satisfaction Problem (CSP). To solve these efficiently, solvers employ a search procedure interleaved with a filtering step known as Arc Consistency (AC). AC prunes the search space by identifying and removing values from variable domains that cannot satisfy a given constraint, given the current assignments of other variables.

Figure 1: Visualization of supports and arc consistency between variable domains.

As shown in Figure 1, AC relies on finding "supports"—values in neighboring domains that satisfy a constraint. If a value $a$ in domain $x$ has no support in domain $y$, it can be safely removed. In hard problems, this process is invoked millions of times, making its efficiency critical to overall solver performance.

The ACS Framework and Residual Data

The primary insight of this work is that search is an incremental process. The state of the problem at one search node is nearly identical to its state at the parent node. Standard AC algorithms, when "plugged in" to a search engine, often ignore this fact, re-calculating supports from scratch or performing expensive state restoration upon backtracking.

The authors propose the Arc Consistency during Search (ACS) framework, which formalizes the interaction between search and filtering through four methods: init, try, backjump, and addInfer. This framework allows for the explicit management of "residual data"—information like the last found support for a value—which can be carried over across search steps.

Algorithm Innovations: The Power of Simplicity

Several algorithms were developed within this framework:

  • ACS-3 and ACS-3.1record: Adaptations of classic algorithms that maintain a last(x, a, y) pointer to the first valid support found.
  • ACS-residue: The standout innovation. Unlike traditional approaches that restore last() pointers to their previous state when the search backtracks, ACS-residue leaves them as "residues." These pointers are reused as starting points in new branches, often finding valid supports immediately without re-scanning the domain.
  • ACS-ADO (Adaptive Domain Ordering): An algorithm that dynamically reorders domains to move deleted values to the end, theoretically speeding up future searches.

Theory vs. Practice: The Overhead Trap

A key finding of the study is the divergence between theoretical complexity and practical wall-clock time. While ACS-ADO offers superior theoretical "node-forward" time complexity, its implementation requires maintaining intricate data structures.

Figure 4: Complex data structures (bags and linked lists) used in Adaptive Domain Ordering (ADO).

As illustrated in Figure 4, the overhead of managing these pointers and "bags" during search outweighs the algorithmic benefits. In contrast, ACS-residue is remarkably simple to implement and maintain, leading to the best overall performance.

Key Results and Conclusion

Experimental evaluations on both random binary CSPs and real-world Radio Link Frequency Assignment Problems (RLFAPs) confirm the superiority of the residue-based approach. On the scen11 RLFAP benchmark, ACS-residue achieved a 40% speedup over standard ACS-3, completing the task in 1.934 seconds compared to 3.265 seconds. Notably, while more complex algorithms like ACS-resOpt and ACS-3.1record performed slightly fewer raw constraint checks, their computational overhead resulted in slower overall wall-clock times.

The success of ACS-residue highlights a vital principle in solver design: simplicity and low overhead often trump theoretical optimality in practice. By treating AC as an integral part of the search process rather than a standalone black box, we can unlock significant efficiency gains through the clever reuse of "leftover" data.

Summary updated

BibTeX
@inproceedings{likitvivatanavong2007arc,
  author = {Chavalit Likitvivatanavong and Yuanlin Zhang and Scott Shannon and James Bowen and Eugene C. Freuder},
  title = {{Arc Consistency during Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure