A Study of Residual Supports in Arc Consistency

Christophe Lecoutre, Fred HemeryIJCAI 2007

Abstract

Arc Consistency (AC) is a cornerstone of Constraint Satisfaction Problem (CSP) solvers, used to prune search spaces by removing inconsistent values. While the classic AC3 algorithm is widely used for its simplicity, its $O(ed^3)$ worst-case time complexity can be inefficient. Conversely, "optimal" algorithms like AC2001 achieve $O(ed^2)$ but introduce significant data-maintenance overhead during backtracking search. This paper introduces AC3rm, a refined algorithm that utilizes multi-directional residual supports (residues). AC3rm maintains the simplicity of AC3 while achieving optimal performance in many practical scenarios and avoiding the overhead of state restoration during search.

Introduction

In the realm of Constraint Satisfaction Problems (CSPs), maintaining Arc Consistency (AC) is essential for efficient solving. The standard algorithm, AC3, is valued for its ease of implementation but criticized for redundant constraint checks. While newer algorithms have reached the theoretical lower bound of $O(ed^2)$ complexity, they often rely on complex data structures to track the "smallest" supports. When integrated into a backtracking search (the MAC algorithm), these structures must be painstakingly reset at each branch, creating a computational burden that can negate theoretical gains.

Methodology: AC3 with Multi-directional Residues (AC3rm)

The authors propose AC3rm, which stands for AC3 with multi-directional residues. The algorithm is built on three core principles:

  1. Residues: Instead of re-scanning a domain from scratch, AC3rm stores the last valid support found for a variable-value pair (the "residue"). Subsequent checks first verify if this residue is still valid before initiating a new search.
  2. Multi-directionality: When a support tuple $(a, b)$ is identified for a constraint between variables $X$ and $Y$, it is recorded as the residue for both $(X, a)$ and $(Y, b)$. This "two-for-one" update significantly reduces the total number of constraint checks.
  3. Lazy Maintenance: Unlike AC2001, AC3rm does not require residues to be the smallest valid supports. This allows for "lazy" maintenance; when the solver backtracks, residues remain in memory. If they are still valid in the new search state, they are used; if not, a new search begins. This eliminates the $O(\mu ed)$ reinitialization cost per branch associated with other optimal algorithms.
Theoretical space and time complexity comparison of arc consistency algorithms.

Complexity and Optimality

While AC3rm retains a worst-case complexity of $O(ed^3)$ for medium-tightness constraints, it achieves the optimal $O(ed^2)$ bound in scenarios where constraints are either very loose or very tight. This "optimality at the edges" makes it highly effective for a wide range of real-world problems.

Experimental Evaluation

The performance of AC3rm was evaluated against AC3, AC2001, and AC3.2 across various benchmarks, including random instances at the phase transition, academic problems, and real-world scheduling and frequency assignment tasks.

The Domino Problem

The Domino problem is a classic stress test designed to expose the weaknesses of "forgetful" algorithms like AC3. In these instances, AC3 repeatedly re-scans domains, leading to explosive growth in constraint checks. As shown in the results below, AC3rm's use of residues effectively mitigates this behavior, matching or exceeding the performance of more complex optimal algorithms.

Performance comparison on Domino problem instances, highlighting the efficiency of AC3rm.

On the Domino-800-800 instance, AC3rm required only 60 seconds and 511M constraint checks, a massive improvement over AC3’s 6,144 seconds and 68,778M checks. Notably, AC3rm even outperformed the theoretically optimal AC2001 (87 seconds) due to its lower overhead.

Backtracking Search (MAC)

When integrated into the Maintaining Arc Consistency (MAC) search procedure, AC3rm consistently ranked as the fastest or second-fastest algorithm. Its advantage stems from the lack of state restoration requirements during backtracking, allowing it to bypass the $O(\mu ed)$ overhead that plagues AC2001 and its variants.

Conclusion

AC3rm represents a significant practical advancement in arc consistency algorithms. By combining the simplicity of AC3 with the efficiency of residual supports and multi-directionality, it offers a robust "middle way" for CSP solvers. It achieves optimal performance in key tightness scenarios and excels in backtracking search environments where data structure maintenance is a bottleneck.

Summary updated

BibTeX
@inproceedings{lecoutre2007study,
  author = {Christophe Lecoutre and Fred Hemery},
  title = {{A Study of Residual Supports in Arc Consistency}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure