Breaking symmetries in all different problems

Jean-Francois PugetIJCAI 2005

Abstract

Constraint Satisfaction Problems (CSPs) frequently encounter performance bottlenecks due to inherent symmetries, which lead to redundant exploration of the search space. This paper introduces a novel approach to eliminate variable symmetries in CSPs featuring the alldifferent constraint. By utilizing Computational Group Theory (CGT) and exploiting the mathematical properties of the alldifferent global constraint, we demonstrate that all variable symmetries can be broken using at most $n-1$ simple binary constraints. Our method, termed Symmetry Breaking Constraints (SBC), serves as an efficient pre-processing step that significantly outperforms existing search-based symmetry-breaking techniques.

Introduction

In combinatorial problems such as scheduling, map coloring, and Sudoku, symmetries—rotations, reflections, or permutations—can exponentially increase the search space. Traditional symmetry-breaking methods, like Lex-leader, often require an impractical number of constraints to be fully effective. This research addresses a common class of CSPs where variables are constrained to take distinct values via the alldifferent constraint. We propose a method to simplify the symmetry-breaking process into a set of linear-time binary constraints, drastically reducing computational overhead.

Methodology

The core of the proposed approach lies in the simplification of lexicographical comparisons. In standard Lex-leader methods, breaking symmetry involves complex comparisons between vectors of variables. However, when an alldifferent constraint is present, these comparisons collapse into strict "less-than" ($v_i < v_j$) relationships between specific variable pairs.

Computational Group Theory (CGT)

To automate the detection of symmetries, we employ the Schreier-Sims algorithm from CGT. This algorithm constructs a stabilizer chain for the problem's symmetry group, identifying the minimal set of variables that must be ordered to break all symmetries.

Linear Constraints and Integration

A key theoretical contribution is the proof that at most $n-1$ binary constraints are sufficient to break all variable symmetries in this context. Furthermore, this method is compatible with the GE-tree approach, allowing for the simultaneous breaking of both variable and value symmetries.

Experimental Evaluation

The SBC method was evaluated on two highly symmetric benchmarks: Graceful Graphs ($K_n \times P_2$) and Most Perfect Magic Squares.

Graceful Graphs

For the $K_n \times P_2$ graph series, the SBC method demonstrated a massive reduction in the search tree. As shown in the table below, for the $K_5 \times P_2$ instance, the number of nodes explored dropped from over 349 million to approximately 53,000, with a corresponding speedup in execution time.

Performance of SBC on Graceful Graphs ($K_n \times P_2$)

Magic Squares

In the Magic Squares benchmark, the efficiency of the pre-processing phase was particularly evident. The time required to compute symmetry-breaking constraints (the 'sym' column) was orders of magnitude lower than that of competing methods like GAP-SBDD. For instance, at $n=12$, SBC required only 0.44 seconds for symmetry computation compared to 2,745 seconds for GAP-SBDD.

Comparison of SBC with GAP-SBDD and GE-tree

Key Insights and Results

The experimental results highlight several advantages of the SBC approach:

  • Efficiency: SBC was up to 30 times faster than search-based methods like GAP-SBDD on Graceful Graph problems.
  • Automation: By integrating with CGT packages like Nauty, the process can be fully automated, removing the need for manual symmetry identification.
  • Pre-processing Advantage: Unlike in-search methods, SBC is a one-time pre-processing step, making it compatible with any standard CSP solver.

Conclusion and Future Work

The SBC method provides a highly efficient solution for breaking variable symmetries in the presence of alldifferent constraints. While the method effectively handles variable and value symmetries, future work will focus on addressing "product symmetries"—combinations of variable and value swaps—which remain a challenge. Additionally, investigating whether similar linear reductions can be applied to other global constraints remains a promising avenue for research.

Summary updated

BibTeX
@inproceedings{puget2005breaking,
  author = {Jean-Francois Puget},
  title = {{Breaking symmetries in all different problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure