On the Inherent Level of LocalConsistency in Constraint Networks

TL;DR

This paper introduces a new property called "constraint looseness" to estimate the inherent local consistency of constraint networks. This helps identify when preprocessing with low-order consistency techniques is futile and provides a foundation for developing more efficient backtracking search algorithms.

What Problem Does This Paper Address?

Constraint networks are a powerful framework for representing problems involving variables, their possible values (domains), and relationships between them (constraints). A key challenge in solving these networks is the presence of "local inconsistencies" – partial assignments that cannot be extended to a full solution, leading to dead ends in search algorithms. To combat this, researchers have developed techniques to enforce "local consistency" (e.g., arc consistency, path consistency), which prune these inconsistencies. However, some constraint networks are inherently consistent to a certain degree, meaning enforcing low-order consistency offers no benefit. This paper addresses two main questions:

  1. How can we efficiently estimate the inherent level of local consistency of a constraint network?
  2. How can this understanding be used to improve constraint satisfaction algorithms, particularly by identifying when preprocessing is unnecessary or by finding "backtrack-free" variable orderings?

Methods

The core contribution of this paper is the introduction of constraint looseness.

  • Constraint Looseness: For a binary constraint (represented by a matrix where 1s indicate allowed value pairs and 0s disallowed pairs), a constraint is m-loose if every row and every column of its matrix has at least m ones. A network is m-loose if all its constraints are m-loose.
  • Theorem 1: This theorem establishes a crucial link: if a binary constraint network has domains of size d or less and its constraints are m-loose, then the network is guaranteed to be strongly ceil(d / (d-m))-consistent. This provides a lower bound on the network's inherent local consistency.
  • Backtrack-Free Orderings: The paper extends these ideas to identify variable orderings that guarantee a solution can be found without backtracking. It builds upon existing work relating variable ordering "width" to local consistency and introduces "directional looseness" to develop a new condition for backtrack-free orderings.
  • FINDORDER Algorithm: An efficient algorithm is presented to find such a backtrack-free ordering if one exists.

Datasets

Not discussed in the paper. The paper focuses on theoretical properties of constraint networks and uses examples like the n-queens problem and graph k-colorability for illustration.

Key Insights and Ideas

  • Looseness as a Predictor: Constraint looseness offers a simple, computationally inexpensive way to predict a network's inherent local consistency. This is a significant improvement over more complex methods for verifying higher levels of consistency.
  • Identifying "Easy" Networks: Networks with loose constraints are often inherently consistent. This means that for such networks, applying low-order consistency preprocessing is often a waste of computational effort.
  • Counter-Intuitive Hardness: The paper presents experimental evidence suggesting that constraint networks with loose constraints can be among the hardest to solve. This is counter-intuitive because individual loose constraints are easy to satisfy. The hardness arises from the complex interplay of many such constraints, leading to many dead ends deep in the search tree.
  • Directional Looseness for Backtracking: The concept of directional looseness provides a more refined condition for finding backtrack-free orderings, which can significantly speed up search.

Key Results

  • Theorem 1: Provides a sufficient condition for a network to be strongly ceil(d / (d-m))-consistent based on domain size and constraint looseness.
  • N-Queens Example: For the n-queens problem, Theorem 1 predicts inherent strong ceil(n/3)-consistency, while the actual level is ceil(n/2) for n ≥ 7. This demonstrates that the theorem provides a lower bound and highlights cases where it underestimates the true consistency.
  • Graph Coloring Example: Graph k-colorability networks are shown to be an example where Theorem 1 is exact, predicting inherent strong k-consistency.
  • Backtrack-Free Ordering Condition: A new condition based on directional looseness and variable ordering width is presented, which guarantees backtrack-free search.
  • FINDORDER Algorithm: An efficient algorithm is provided to find such backtrack-free orderings.

Limitations and Future Work

  • Lower Bound: Theorem 1 provides a sufficient but not necessary condition, meaning it gives a lower bound on inherent local consistency. The actual level of consistency can be higher.
  • Experimental Findings: The paper notes that while loose constraints imply high inherent consistency, these networks can still be computationally hard. This suggests that inherent consistency alone doesn't fully explain problem hardness.
  • Future Work: The authors suggest exploring how constraint looseness can be used to develop more effective domain and variable ordering heuristics. They also plan to investigate how looseness can improve the average-case efficiency of local consistency algorithms by predicting when subnetworks are already consistent.

Summary updated

BibTeX
@inproceedings{1994inherent,
  title = {{On the Inherent Level of LocalConsistency in Constraint Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure