Introduction
Symmetry in Boolean Satisfiability (SAT) problems often leads to redundant search spaces, where solvers waste significant time exploring equivalent assignments. For instance, if variables $x$ and $y$ are interchangeable, a solver might independently prove that both $(x=1, y=0)$ and $(x=0, y=1)$ are unsatisfiable. To mitigate this, researchers use Symmetry Breaking Predicates (SBPs)—additional constraints that restrict the search to a single "lexicographical leader" from each set of symmetric assignments. However, traditional SBP constructions often grow quadratically ($O(n^2)$) with the number of variables, sometimes introducing overhead that outweighs the benefits of symmetry breaking.
Methodology: Surgical SBP Construction
This paper proposes a more efficient approach to constructing SBPs by focusing on the internal structure of symmetries and optimizing the logical representation.
Exploiting Cycle Structure and Irredundant Bits
Instead of treating symmetries as monolithic transformations, the authors decompose them into disjoint cycles (e.g., $x_1 \to x_2 \to x_3 \to x_1$). By analyzing these cycles, they identify "irredundant bits" that can be safely omitted from the SBP:
- Fixed Points: Variables not moved by the symmetry.
- Cycle Terminals: The last variable in a cycle, as its value is implicitly constrained by the others.
- Phase-Shifts: Symmetries that map a variable to its negation. The authors prove that once a phase-shift is encountered in the variable ordering, all subsequent bit predicates for that symmetry become redundant.
Linear Chaining
Standard SBP formulations use recursive "if-then" logic, leading to a quadratic number of clauses. The authors introduce auxiliary "chaining variables" ($p_i$) to act as markers, allowing the same symmetry-breaking logic to be expressed with a linear number of clauses ($O(n)$).
Experimental Evaluation
The proposed method was evaluated on several benchmark families, including Pigeon-hole instances (Hole-n), expander graph instances (Urq), and real-world circuit routing problems (GRoute, FPGARoute).
Key Results
The results demonstrate that the linear construction significantly reduces the size of the added constraints. For the GRoute benchmark, the traditional quadratic method added over 63 million literals, whereas the new linear method required only 43,506—a 1,400x reduction.
More importantly, these smaller SBPs translate into massive performance gains. On the FPGARoute benchmarks, the solver achieved speedups of up to 3,635x compared to the baseline without symmetry breaking.
Discussion and Insights
- Sparsity and Efficiency: Most symmetry generators are sparse, affecting only a small fraction of variables. Focusing on these "moved" variables is crucial for efficiency.
- Heuristic Sensitivity: Interestingly, in some cases like the
2pipebenchmark, the larger quadratic SBPs accidentally improved performance by providing more variables for the solver's branching heuristics (e.g., VSIDS) to utilize. This suggests a complex interplay between formula size and solver heuristics. - Limitations: The method relies on external tools like
nautyfor symmetry discovery. Furthermore, while breaking symmetries based on generators is highly efficient, it does not necessarily break all possible symmetries in the group.
Conclusion
By combining cycle-based analysis with linear chaining, this work provides a scalable framework for symmetry breaking in SAT. The resulting predicates are significantly smaller and lead to order-of-magnitude speedups on highly symmetric benchmarks, making symmetry breaking a more practical tool for industrial-scale SAT solving.
Summary updated