Adaptive Neighborhood Inverse Consistency as Lookahead for Non-Binary CSPs

Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian BessiereAAAI 2011 · DOI

Abstract: Constraint Satisfaction Problems (CSPs) are fundamental to various domains, including scheduling, logistics, and hardware verification. Solving these problems efficiently requires a balance between search and inference. This paper explores Relational Neighborhood Inverse Consistency (RNIC), a technique designed to prune the search space of non-binary CSPs by leveraging the structure of the problem's dual graph. We present a suite of RNIC variations—wRNIC, triRNIC, and wtriRNIC—and an adaptive selection mechanism, selRNIC, which uses a decision tree to choose the most effective consistency level based on problem topology. Experimental results on benchmark datasets demonstrate that RNIC can significantly reduce backtracking, often leading to backtrack-free solutions for complex instances.

Introduction

The efficiency of CSP solvers relies heavily on "lookahead" strategies that prune inconsistent values before they lead to exhaustive search failures. While Generalized Arc Consistency (GAC) is the industry standard, it often fails to capture the deep dependencies present in non-binary constraints (constraints involving more than two variables). Higher-order consistency techniques, such as Neighborhood Inverse Consistency (NIC), were originally proposed for binary constraints but struggled to scale to the non-binary case due to memory and computational overhead. This research bridges that gap by introducing Relational Neighborhood Inverse Consistency (RNIC), focusing on the relationships between constraints in the dual graph.

Relational Neighborhood Inverse Consistency (RNIC)

RNIC operates on the dual graph of a CSP, where nodes represent constraints and edges represent shared variables. The core idea is to ensure that every valid combination of values (tuple) in a constraint can be extended to all neighboring constraints in the dual graph. To avoid the memory explosion associated with relational joins, the authors implement RNIC using a localized backtrack search on the subproblem formed by a constraint and its immediate neighbors.

The strength of RNIC can be adjusted by modifying the underlying graph structure. The authors define several variations:

  • wRNIC (Weak): Operates on a "minimal" dual graph to save time on very dense networks.
  • triRNIC (Strong): Triangulates the dual graph to improve the "communication" between constraints, boosting pruning power.
  • wtriRNIC: A hybrid approach combining features of both.
Figure 1: Hierarchy of relational consistency levels, showing the relationship between GAC, RNIC, and its variants.

As shown in Figure 1, these methods form a hierarchy of consistency strengths, where RNIC and its variants provide significantly more pruning power than standard GAC.

Adaptive Selection with selRNIC

A key contribution of this work is the recognition that the "best" consistency level depends on the problem's topology. High density in the dual graph can make strong RNIC variants too slow, while sparse graphs with long cycles might benefit from triangulation. To address this, the authors introduced selRNIC, an adaptive selector that analyzes the problem at the start of the search.

Figure 2: The decision tree used by selRNIC to automatically select the most appropriate graph representation based on dual graph density and other topological metrics.

The selector uses a decision tree (Figure 2) to evaluate metrics such as the density of the original dual graph ($d^{Go}$) and the relative densities of the triangulated and minimal versions. This allows the solver to automatically tune its lookahead strategy, applying stronger inference only where it is likely to be cost-effective.

Experimental Results

The proposed methods were evaluated using benchmarks from the CSP Solver Competition, including aim-100 (3-SAT), lexVg (lexicographical constraints), modifiedRenault (industrial configuration), and ssa (circuit analysis).

Key findings include:

  • Backtrack-Free Search: On several difficult benchmarks, RNIC enabled the solver to find solutions without any backtracking. For example, in the lexVg benchmark, selRNIC correctly identified that triRNIC was necessary, resulting in nearly all instances being solved backtrack-free.
  • Superior Coverage: RNIC completed more instances than GAC on benchmarks like aim-100.
  • Solving Hard Instances: The algorithm successfully solved instances of ssa and aim-200 that were previously unsolvable by other methods in the study.

Conclusion

By focusing on relational dependencies and employing an adaptive selection strategy, RNIC provides a powerful and flexible tool for solving non-binary CSPs. The ability to automatically adjust the strength of inference based on problem topology allows solvers to handle a wider range of complex real-world problems more efficiently. Future work will focus on refining selection policies and integrating these techniques into general-purpose solvers with modern heuristics.

Summary updated

BibTeX
@inproceedings{woodward2011adaptive,
  author = {Robert J. Woodward and Shant Karakashian and Berthe Y. Choueiry and Christian Bessiere},
  title = {{Adaptive Neighborhood Inverse Consistency as Lookahead for Non-Binary CSPs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.1609/aaai.v25i1.8059},
}
Figure