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.
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.
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
lexVgbenchmark,selRNICcorrectly identified thattriRNICwas 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
ssaandaim-200that 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