Improvements of Symmetry Breaking During Search

Zichen ZhuIJCAI 2015

Abstract

Symmetry in Constraint Satisfaction Problems (CSPs) often leads to redundant search effort, as solvers explore branches that are identical under transformation. While Symmetry Breaking During Search (SBDS) provides a dynamic solution, its practical utility is often limited by high computational overhead and incomplete pruning. This paper introduces three significant optimizations: Recursive SBDS (ReSBDS) for enhanced pruning, the incNGs global constraint for efficient nogood management, and lazy propagators (WNC/GWIC) for reduced consistency-checking costs. Experimental results on Balanced Incomplete Block Design (BIBD) benchmarks demonstrate that these techniques can reduce search tree size by half and achieve speedups of up to 16.6x, outperforming established static methods like LexLeader.

Introduction

In combinatorial search, symmetries—such as row or column permutations in a matrix—can exponentially increase the search space. Traditional approaches to symmetry breaking are either static, adding constraints before search (e.g., LexLeader), or dynamic, adding "nogood" constraints during search (SBDS). However, standard SBDS often suffers from a "mountain of weak constraints" that slows down the solver. This paper addresses these efficiency and effectiveness gaps through a multi-pronged algorithmic approach.

Methodology

The authors propose three core improvements to dynamic symmetry breaking:

1. Recursive SBDS (ReSBDS)

Standard partial SBDS only breaks explicitly provided symmetries. ReSBDS extends this by adding constraints recursively to prune symmetric nodes of subtrees that have already been pruned. This allows the solver to break compositions of symmetries without requiring an exhaustive initial list, effectively closing the gap between partial SBDS and full symmetry breaking.

2. Increasing-Nogoods Global Constraint (incNGs)

SBDS typically generates numerous individual nogoods. The authors observed that these nogoods are often semantically related and grow in length (the "increasing" property). By bundling these into a single global constraint, the solver reduces management overhead and enables more efficient filtering algorithms.

3. Weak-Nogood Consistency (WNC & GWIC)

Maintaining Generalized Arc Consistency (GAC) on symmetry constraints is computationally expensive. Borrowing the "watched literal" concept from SAT solvers, the authors developed lazy propagators. These propagators only trigger when specific assignments are made, drastically reducing the cost of checking symmetry constraints while maintaining effective pruning.

Performance comparison of ParSBDS with different consistency levels and global constraints.

Experimental Evaluation

The methods were implemented in the Gecode solver and evaluated using the Balanced Incomplete Block Design (BIBD) problem, a standard benchmark characterized by intense matrix symmetries. The evaluation compared the proposed dynamic methods against established static methods (DoubleLex and LexLeader) and standard ParSBDS.

Key Results

The experiments revealed dramatic improvements across several metrics:

  • Search Tree Reduction: The light version of the recursive method (LReSBDS) reduced the number of failures (search nodes) to approximately half that of standard ParSBDS. For instance, in the (7,3,5) BIBD instance, failures dropped from 83,578 to 41,978.
  • Computational Speedups: The incNGs global constraint made ParSBDS up to 8.5x faster. More impressively, the lazy propagators (WNC) achieved speedups of up to 16.6x over standard GAC propagators.
  • Comparison with Static Methods: The optimized dynamic configuration (LReSBDS with GWIC) outperformed widely-used static methods like LexLeader and DoubleLex. In several instances, the dynamic approach was significantly faster while maintaining a comparable or smaller search tree.
Comprehensive comparison of static (DoubleLex, LexLeader) and dynamic (ParSBDS, LReSBDS) symmetry breaking methods.

Conclusion

This work demonstrates that dynamic symmetry breaking can be highly competitive with, and often superior to, static methods if implemented efficiently. By exploiting the structure of nogoods and utilizing lazy propagation techniques, the overhead of SBDS is significantly mitigated. Future research will explore the interaction between these symmetry-breaking methods and modern search heuristics to find the optimal balance between pruning power and computational cost.

Summary updated

BibTeX
@inproceedings{zhu2015improvements,
  author = {Zichen Zhu},
  title = {{Improvements of Symmetry Breaking During Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure