On Neighborhood Singleton Consistencies

Anastasia Paparrizou, Kostas StergiouIJCAI 2017 · DOI

TL;DR

This paper introduces a new family of "neighborhood singleton consistencies" for Constraint Satisfaction Problems (CSPs). These new methods offer a sweet spot between the strong pruning power of complex "triangle-based" consistencies and the ease of implementation of simpler "singleton" ones, significantly outperforming existing techniques on a wide range of problems.

What Problem Does This Paper Address?

Constraint Satisfaction Problems (CSPs) are a fundamental area in Artificial Intelligence, where the goal is to find assignments of values to variables that satisfy a set of constraints. A common technique to solve CSPs is through search, often enhanced by "consistency techniques" that prune the search space by removing inconsistent values from variable domains.

While Arc Consistency (AC) is the most widely used technique, stronger methods like Restricted Path Consistency (RPC) and maxRPC exist and can significantly speed up search. However, these are often complex to implement. On the other hand, "singleton consistencies" like Singleton Arc Consistency (SAC) are easy to implement but can be computationally too expensive. Recently, Neighborhood SAC (NSAC) was proposed as a compromise, applying AC only to the neighborhood of a variable during a singleton check. This paper aims to find an even better balance, developing new singleton consistencies that are as efficient as triangle-based methods but as easy to implement as NSAC.

Methods

The paper proposes a family of new singleton consistencies inspired by RPC and maxRPC, building upon the idea of Neighborhood SAC (NSAC). The core idea is to perform a "singleton check" on a variable's value (i.e., temporarily assign a value to a variable and see if consistency can be maintained).

Key methodological contributions include:

  • NS1pAC (Neighborhood Singleton 1-pass Arc Consistent): A weaker version of NSAC where AC is applied in a single pass over the variable's neighborhood.
  • Condition FC: A crucial condition that prioritizes processing constraints involving the currently checked variable and its neighbors before applying the 1-pass AC. This condition significantly enhances the pruning power of NS1pAC, making it strictly stronger than maxRPC.
  • RNSAC (Restricted Neighborhood SAC) and RsNSAC (Restricted sub-Neighborhood SAC): These consistencies are inspired by RPC. They involve applying AC to a restricted part of the variable's neighborhood (either the entire neighborhood for RNSAC or a specific sub-graph for RsNSAC) only if a singleton domain is detected in the neighborhood after applying Condition FC.
  • 1-pass variants (RNS1pAC, RsNS1pAC): Similar to RNSAC and RsNSAC, but using 1-pass AC instead of full AC.

The paper also provides a theoretical analysis of the pruning power of these new consistencies, comparing them to existing ones like AC, RPC, maxRPC, and NSAC. An algorithm (Algorithm 1, RNSQ) is presented for implementing these new methods, highlighting its simplicity.

Datasets

The experiments were conducted on 16 classes of binary CSPs from the C.Lecoutre's XCSP repository, totaling 1054 instances. These classes include rlfap, graph coloring, qcp, qwh, bqwh, driver, haystacks, hanoi, pigeons, black hole, ehi, queens, queensAttacking, queensKnights, geometric, and composed.

Key Insights and Ideas

  • The "Sweet Spot" is Achievable: The paper successfully demonstrates that it's possible to achieve strong pruning power comparable to triangle-based consistencies while maintaining the implementation simplicity of singleton methods.
  • Condition FC is a Game Changer: The introduction of Condition FC significantly boosts the effectiveness of 1-pass AC in singleton checks, making NS1pAC (with FC) strictly stronger than maxRPC and enabling efficient pruning.
  • RNSAC Outperforms: Among the proposed methods, RNSAC emerges as the most effective, offering a strong balance between pruning power and computational cost.
  • Singleton Consistencies Shine in Practice: Contrary to the common perception that full singleton consistencies are too expensive, this work shows that well-designed neighborhood singleton methods can be highly competitive and even outperform established techniques on many problems.
  • Simplicity Matters: The proposed algorithms are described as "very simple," which is a significant advantage for practical adoption in existing CSP solvers.

Key Results

  • Theoretical Superiority: The paper proves that the proposed singleton consistencies (especially RNSAC and its variants) are generally stronger than RPC and maxRPC.
  • Experimental Dominance: In experiments, the proposed neighborhood singleton consistencies, particularly RNSAC, significantly outperformed AC, IRPC, and ImaxRPC on a wide range of problems, often by orders of magnitude in terms of node visits and execution time.
  • RNSAC is the Champion: RNSAC was found to be the best among the proposed methods, cutting down the search tree size almost as much as NSAC but with considerably lower run times.
  • Efficiency Gains: For many instances, RNSAC solved problems that IRPC timed out on, demonstrating its practical advantage.
  • Queens Exception: The singleton methods performed less well on the "queens" problem class, likely due to its complete constraint graph, which makes NSAC equivalent to SAC and thus computationally expensive.

Limitations and Future Work

  • Dom/wdeg Heuristic: The paper notes that while the neighborhood methods perform well on many problems, they are considerably slower on rlfap and queens when using the dom/wdeg heuristic.
  • Non-binary Constraints: The authors suggest that exploring the viability of neighborhood singleton consistencies for non-binary constraints is a promising future direction. This is particularly interesting because existing methods for non-binary constraints are often complex.
  • Further Optimization: While the proposed algorithms are simple, further optimizations might be possible for specific applications.

Summary updated

BibTeX
@inproceedings{paparrizou2017neighborhood,
  author = {Anastasia Paparrizou and Kostas Stergiou},
  title = {{On Neighborhood Singleton Consistencies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/102},
}
Figure