Neighborhood Inverse Consistency Preprocessing

AAAI 1996

TL;DR

This paper introduces "Neighborhood Inverse Consistency" (NIC), a novel preprocessing technique for constraint satisfaction problems (CSPs). NIC significantly reduces search effort by intelligently pruning variable domains, outperforming traditional arc consistency methods, especially on difficult problems, without incurring prohibitive space costs.

What Problem Does This Paper Address?

Constraint Satisfaction Problems (CSPs) are a fundamental framework for modeling many AI problems, where the goal is to find an assignment of values to variables that satisfies a set of constraints. Solving CSPs can be computationally expensive, especially for large and complex problems. Preprocessing techniques are often employed to reduce the search space before the main solving process begins. While standard methods like arc consistency (AC) prune variable domains, they can be insufficient for hard problems, and higher-order consistency methods, though more powerful, often suffer from excessive time or space costs. This paper addresses the challenge of achieving more effective pruning with limited computational resources, particularly focusing on the often-overlooked space complexity of preprocessing.

Methods

The paper introduces Neighborhood Inverse Consistency (NIC), which combines two key ideas:

  • Inverse Consistency: Unlike traditional consistency methods that focus on finding solutions to subproblems, inverse consistency focuses on removing values that cannot be part of any solution to a subproblem involving additional variables. This is crucial because it avoids the potentially prohibitive space costs associated with storing solutions to subproblems. The space requirement for inverse consistency is at worst linear.
  • Neighborhood Consistency: Instead of enforcing consistency uniformly across the entire problem, NIC targets the "neighborhood" of a variable. Specifically, for a given value of a variable, it examines the subproblem induced by that variable and its immediate neighbors. This "targeted" approach aims to "skim the cream" by focusing on highly relevant subproblems for maximum pruning with limited effort.

The paper also proposes One-Pass Neighborhood Inverse Consistency (ONIC), a simplified version of NIC that processes each variable only once, sacrificing some propagation for speed. They also implement Path Inverse Consistency (PIC), another higher-order consistency technique.

The search algorithm used for evaluation is FC-CBJ-DMD, a combination of forward checking, conflict-directed backjumping, and dynamic minimum domain size ordering.

Datasets

The authors generated test problems using a random problem generator. They specified:

  • Number of variables: 100
  • Number of values per variable: 6
  • Tightness: 0.5 and 0.4 (a measure of how constraining constraints are)
  • Density: Varied to explore the "complexity peak" or "phase transition" area where problems are hardest.

The problems were generated to be connected constraint graphs.

Key Insights and Ideas

  • Inverse Consistency's Space Advantage: The core insight is that inverse consistency can achieve significant pruning without the high space overhead of methods that store subproblem solutions. This is critical for large-scale CSPs.
  • Targeted Pruning with Neighborhoods: Focusing consistency enforcement on the neighborhood of a variable (NIC) is more efficient than uniform application, allowing for a higher payoff for a limited cost.
  • NIC Outperforms AC on Hard Problems: Even though NIC has a higher preprocessing cost than AC, it drastically reduces the subsequent search time on difficult problems, leading to a much lower total cost.
  • "Skimming the Cream": The neighborhood approach is akin to finding the "low-hanging fruit" for pruning, making it more cost-effective than methods that try to achieve full consistency everywhere.
  • NIC Implies Arc Consistency: A key theoretical result is that both NIC and PIC imply arc consistency, meaning they prune at least as many values as AC.

Key Results

  • Significant Speedups: For the hardest problems tested (at tightness 0.5 and density 0.02), NIC preprocessing followed by search was dramatically faster than AC preprocessing followed by search. For instance, one problem that took over 3 minutes with AC+S was solved in about a tenth of a second with NIC+S.
  • NIC Excels in Worst-Case Scenarios: Figures 6 and 7 show that NIC is particularly effective at keeping down the maximum effort required, outperforming AC on the most difficult problems. This is valuable for real-time applications where response time fluctuations are undesirable.
  • ONIC is a Viable Alternative: While not as powerful as full NIC, ONIC also shows good performance, suggesting that even a single pass of neighborhood inverse consistency can be beneficial.
  • Space Efficiency: The paper emphasizes that NIC does not incur high space costs, a significant advantage over other higher-order consistency methods.

Limitations and Future Work

  • Algorithm Implementation: The authors acknowledge that their NIC and ONIC algorithms were implemented in a straightforward manner, suggesting room for improvement, particularly in avoiding redundant processing of overlapping subproblems.
  • Information Retention: They propose that information obtained during subproblem solutions could be profitably retained, even at some space cost, to further enhance performance.
  • Hybrid Approaches: The paper suggests interleaving inverse consistency with search in hybrid algorithms, similar to forward checking, as a promising avenue for future research.
  • Higher-Order Inverse Consistency: Studying higher-order k-inverse consistency and combining it with k-consistency is also suggested.
  • "Targeted" Consistency: Exploring other forms of "targeted" consistency, based on problem-specific understanding, could also be beneficial.

Summary updated

BibTeX
@inproceedings{1996neighborhood,
  title = {{Neighborhood Inverse Consistency Preprocessing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure