Path-Consistency: When Space Misses Time

AAAI 1996

TL;DR

This paper introduces PC-7, a novel path-consistency algorithm for Constraint Satisfaction Problems (CSPs) that significantly reduces memory requirements compared to existing methods like PC-6. While PC-7 has a higher theoretical time complexity, its practical efficiency and ability to handle larger CSPs make it a compelling alternative.

What Problem Does This Paper Address?

Constraint Satisfaction Problems (CSPs) are fundamental in artificial intelligence and operations research, involving finding assignments of values to variables that satisfy a set of constraints. Preprocessing techniques, particularly filtering algorithms that enforce local consistency, are crucial for pruning the search space and making CSPs tractable. Arc-consistency and path-consistency are two such properties. While arc-consistency algorithms are efficient, path-consistency offers more powerful filtering but has historically suffered from high memory demands, limiting its practical application. Existing state-of-the-art path-consistency algorithms like PC-6, while an improvement over PC-4, still require substantial memory (O(n³d²)), making them impractical for large CSPs. This paper aims to bridge this gap by developing a path-consistency algorithm that prioritizes space efficiency without sacrificing practical performance.

Methods

The paper proposes PC-7, a new path-consistency algorithm. PC-7 builds upon the "minimal support" principle, similar to PC-6, but with a key difference: it does not store supports. Instead, when a propagation requires checking for supports, PC-7 re-evaluates them from scratch. This design choice drastically reduces the space complexity.

The core components of PC-7 include:

  • Initialization: Similar to PC-6, it identifies and removes pairs of values that lack any support and adds them to a propagation list.
  • Propagation: When a pair of values is removed, PC-7 triggers propagation to related constraints. Crucially, it restarts the search for supports from the beginning of the domain for each check, unlike PC-6 which continues from the last known support.
  • Withoutsupport function: A helper function to determine if a given pair of values has a support within a specific domain.

This approach leads to a space complexity of O(n²d²), which is the best among known path-consistency algorithms, but a theoretical time complexity of O(n³d⁴). However, the authors argue that the simplicity of PC-7's data structures and algorithm leads to superior practical performance.

Datasets

The paper does not introduce new datasets. Instead, it uses randomly generated CSPs based on the model proposed by Hubbe & Freuder (1992). This model allows for varying parameters such as the number of variables (n), domain size (d), constraint tightness (t), and constraint graph density (cd). Experiments were conducted with various combinations of these parameters.

Key Insights and Ideas

  • The Space-Time Trade-off in Path-Consistency: The paper highlights that achieving optimal theoretical time complexity for path-consistency (like PC-6) can come at the cost of prohibitive memory usage, rendering it impractical. PC-7 demonstrates that relaxing theoretical time complexity can lead to significant practical gains in space efficiency and overall performance.
  • The Cost of Stored Supports: PC-6's reliance on storing supports, while theoretically efficient, incurs significant overhead in terms of data structure management and pointer manipulation. PC-7's decision to re-compute supports on demand, despite a higher theoretical time complexity, bypasses this overhead, leading to faster execution in practice.
  • Practical Efficiency Over Theoretical Optimality: The experiments strongly suggest that for many real-world CSPs, PC-7's simpler implementation and reduced memory footprint result in faster execution times and the ability to handle much larger problems than PC-6, even though PC-6 has a better theoretical time complexity.
  • Constant Domain Size Advantage: When the domain size (d) is a constant, PC-7's time complexity becomes O(n³), matching PC-6 and becoming theoretically optimal in both time and space. This scenario is common in many practical applications.

Key Results

  • Space Complexity: PC-7 achieves a space complexity of O(n²d²), which is the best among known path-consistency algorithms. This is a significant improvement over PC-6's O(n³d²).
  • Time Complexity: PC-7 has a theoretical time complexity of O(n³d⁴), which is worse than PC-6's O(n³d³). However, in practice, PC-7 often outperforms PC-6 in terms of CPU time.
  • Handling Larger CSPs: PC-7 was able to handle CSPs with n=32 and d=8, whereas PC-6 struggled or was impossible to run due to memory constraints. For larger instances (n=64, n=128), PC-7 showed significantly faster execution times.
  • Performance Comparison: Experiments showed that PC-7 performed comparably to or better than PC-2 and PC-4 in terms of consistency checks and CPU time, while offering superior space efficiency.

Limitations and Future Work

  • Theoretical Time Complexity: The paper acknowledges that PC-7's theoretical time complexity of O(n³d⁴) is higher than PC-6's O(n³d³).
  • Future Work: The authors suggest that it would be interesting to explore whether the approach of PC-7 can be applied to temporal reasoning problems, as described in Allen (1983).

Summary updated

BibTeX
@inproceedings{1996path,
  title = {{Path-Consistency: When Space Misses Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure