Filtering Nogoods Lazily in Dynamic Symmetry Breaking During Search

Jimmy H. M. Lee, Zichen ZhuIJCAI 2015

Abstract

Symmetry breaking is a critical technique for solving Constraint Satisfaction Problems (CSPs) efficiently. While dynamic methods like Symmetry Breaking During Search (SBDS) offer flexibility by generating "nogoods" during search, they often suffer from significant computational overhead due to the massive number of constraints produced. This paper proposes a "lazy" approach to nogood filtering by introducing Weak-Nogood Consistency (WNC) and a single-watched-literal propagator. By trading off some pruning power for execution speed, the proposed methods, including Generalized Weak-incNGs Consistency (GWIC), significantly reduce search overhead. Experimental results on standard benchmarks demonstrate that these lazy dynamic methods can outperform state-of-the-art static symmetry-breaking techniques.

Introduction

In the realm of Constraint Satisfaction Problems (CSPs), symmetry represents a significant challenge. Symmetries allow for multiple equivalent representations of the same state, leading solvers to redundantly explore symmetric branches of the search tree that are guaranteed to be fruitless if their counterparts have already failed. To combat this, researchers employ symmetry-breaking techniques, categorized into static and dynamic methods.

Static methods, such as LexLeader or DoubleLex, add constraints before the search begins. While efficient, they can be rigid. Dynamic methods, notably Symmetry Breaking During Search (SBDS), adapt to the search process by adding "nogoods"—logical implications that prevent the solver from revisiting symmetric states. However, the sheer volume of nogoods generated often leads to a "bottleneck" where maintaining Generalized Arc Consistency (GAC) on thousands of constraints becomes computationally prohibitive, sometimes making dynamic methods slower than their static counterparts.

Methods: Lazy Filtering and Weak Consistency

The core contribution of this work is the shift from expensive, full consistency checks to a more efficient "lazy" approach. The authors introduce Weak-Nogood Consistency (WNC). Unlike GAC, which ensures every constraint is fully pruned at every step, WNC only ensures that a nogood is enforced once its entire "if" condition is met.

To implement WNC efficiently, the authors developed LazyNgProp, a propagator utilizing a "watched literal" technique. While standard propagators typically monitor two literals to detect potential violations, LazyNgProp only watches a single assignment. The propagator remains inactive until that specific assignment occurs, drastically reducing the frequency of constraint checks.

Furthermore, the authors exploit the inherent structure of SBDS nogoods. Because these nogoods are often "increasing" (where each subsequent nogood is a superset of the previous), they proposed Generalized Weak-incNGs Consistency (GWIC). This allows a global constraint, incNGs, to monitor an entire set of related nogoods by watching just one assignment, further minimizing overhead.

Experimental Evaluation

The proposed methods were evaluated against three classic combinatorial benchmarks: Error Correcting Code - Lee Distance (ECCLD), the Cover Array Problem (CA), and Balanced Incomplete Block Design (BIBD). These benchmarks are characterized by high degrees of symmetry, making them ideal for testing symmetry-breaking efficiency.

Table 1: Performance comparison on BIBD benchmarks, showing LReSBDS variants outperforming static methods.

Key Results and Insights

The experimental results highlight a "less is more" paradox: using a weaker consistency (WNC) often leads to better overall performance. Although WNC provides less pruning than GAC, its extreme speed allows the solver to backtrack and explore the search space much faster. In some instances, this rapid exploration triggers the generation of more nogoods, which can break symmetries that a slower, more rigorous GAC propagator might have missed.

As shown in Figure 1, the lazy dynamic approach (LReSBDS) consistently outperformed established static methods like LexLeader and DoubleLex on BIBD benchmarks. Specifically, the LReSBDS_GWIC method was found to be up to 7.9 times faster than LexLeader. Across various tests, the lazy WNC versions were significantly faster than their GAC-enforcing counterparts, with speedups reaching up to 16.67 times in certain BIBD configurations.

Table 2: Performance comparison on ECCLD and CA benchmarks, demonstrating the scalability of lazy nogood filtering.

The efficiency of the lazy propagator is also reflected in its space complexity, which is $O(1)$ per nogood or global constraint. This lightweight memory footprint is crucial when dealing with the millions of nogoods that can be generated during complex searches.

Conclusion and Future Work

This paper demonstrates that lazy nogood filtering is a powerful strategy for dynamic symmetry breaking. By prioritizing execution speed over exhaustive pruning, the proposed WNC and GWIC consistencies overcome the traditional overhead associated with SBDS. Future research directions include investigating the impact of WNC on more complex "composition" symmetries and integrating these lazy filters with automated symmetry detection systems. While there is a potential for increased search tree size due to reduced pruning, the massive gains in per-node processing speed make this a highly effective trade-off for many symmetric CSPs.

Summary updated

BibTeX
@inproceedings{lee2015filtering,
  author = {Jimmy H. M. Lee and Zichen Zhu},
  title = {{Filtering Nogoods Lazily in Dynamic Symmetry Breaking During Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure