Adaptive Singleton-Based Consistencies

Amine Balafrej, Christian Bessiere, El-Houssine Bouyakhf, Gilles TrombettoniAAAI 2014 · DOI

Abstract: Constraint Satisfaction Problems (CSPs) often require a balance between the pruning power of high-level consistencies and the computational overhead they incur. This paper presents APOAC, an adaptive version of the Partition-One-Arc Consistency (POAC) algorithm. By dynamically learning the utility of singleton tests during search, APOAC maintains high pruning efficiency while significantly reducing redundant computations. Experimental results on hard CSP benchmarks demonstrate that APOAC-n outperforms standard Arc Consistency (AC) by over 50% in CPU time and full POAC by over 70%.

Introduction

In Constraint Satisfaction Problems (CSPs), solvers employ consistency techniques to prune values that cannot belong to any solution, thereby reducing the search space. While Arc Consistency (AC) is the industry standard due to its speed, it often fails to detect contradictions that stronger, "singleton-based" consistencies can identify. Singleton Arc Consistency (SAC) and Partition-One-Arc Consistency (POAC) perform "singleton tests"—temporarily assigning a value to a variable to check for immediate contradictions.

However, the computational cost of these stronger methods often outweighs their benefits, especially when solvers spend excessive time on tests that yield no pruning. This paper introduces Adaptive POAC (APOAC), which bridges this gap by learning how many singleton tests are necessary at different stages of the search process.

The APOAC Framework

APOAC is built upon an optimized base algorithm, POAC1, which uses counters to track value deletions across the network, providing more global pruning than standard SAC. The core of APOAC is its adaptive mechanism, which alternates between two distinct phases:

  1. Learning Phase: For a short sequence of search nodes, the solver performs a high number of singleton tests. It monitors the "Volume" of the problem—defined as the logarithm of the product of domain sizes—and records the rank of tests that contribute to significant pruning.
  2. Exploitation Phase: For a subsequent, longer sequence of nodes, the solver applies a learned "cutoff" ($k$). It performs only the first $k$ singleton tests, stopping early even if a fixpoint has not been reached. This prevents the solver from wasting time on the "long tail" of tests that offer diminishing returns.
Figure 1: Comparison of convergence between POAC and SAC. POAC reaches a fixpoint with significantly fewer singleton tests by pruning values across the entire network.

Heuristics for Cutoff Selection

The authors explored two primary heuristics for determining the cutoff $k$:

  • Last Reduction (LR): The rank of the final test that deleted any value.
  • Last Drop (LD): The rank of the last test that caused a significant drop in problem volume, determined by a ratio $\beta$.

To aggregate observations from multiple learning nodes, the researchers found that using the 70th percentile of recorded values was more robust than a simple median.

Experimental Evaluation

The researchers evaluated APOAC against standard AC and full POAC using hard instances from the 2009 CSP Competition, including both binary (e.g., mug, Qwh-20) and n-ary (e.g., TSP, Renault) problem classes.

Key Results and Insights

A primary insight of the study is the "Long Tail" problem: in most search nodes, a small fraction of singleton tests performs the vast majority of pruning. APOAC successfully identifies and eliminates these redundant tests. Furthermore, if the learned cutoff drops to zero, APOAC effectively reverts to standard AC, ensuring it does not impose unnecessary overhead on easier problem segments.

Figure 2: Number of solved instances versus CPU time. APOAC variants, particularly APOAC-n, show superior scaling and solve more instances within the time limit compared to AC and full POAC.

On n-ary problems, the APOAC-n variant achieved a 51% reduction in CPU time compared to AC and a 76% reduction compared to full POAC. While full POAC often timed out on instances like Renault due to its heavy overhead, APOAC's adaptive mechanism allowed it to remain competitive with the faster AC algorithm while still benefiting from POAC's pruning power where needed.

Conclusion

APOAC demonstrates that adaptive consistency is a viable path toward more efficient CSP solvers. By treating consistency level as a dynamic parameter rather than a static choice, solvers can achieve the pruning power of strong consistencies without the crippling computational costs. Future work may extend this adaptive framework to other high-level consistencies, potentially leading to a universal adaptive engine for constraint satisfaction.

Summary updated

BibTeX
@inproceedings{balafrej2014adaptive,
  author = {Amine Balafrej and Christian Bessiere and El-Houssine Bouyakhf and Gilles Trombettoni},
  title = {{Adaptive Singleton-Based Consistencies}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.9120},
}
Figure