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.
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.
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