Symmetry Propagation: Improved Dynamic Symmetry Breaking in SAT
- 1 November 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1 (10823409) , 49-56
Abstract
For constraint programming, many well performing dynamic symmetry breaking techniques have been devised. For propositional satisfiability solving, dynamic symmetry breaking is still either slower or less general than static symmetry breaking. This paper presents Symmetry Propagation, which is an improvement to Lightweight Dynamic Symmetry Breaking, a dynamic symmetry breaking approach from CP. Symmetry Propagation uses any given symmetry as a propagator, and as a result is a general symmetry breaking technique. Experiments with an implementation in the SAT solver Minisat show that on many benchmarks, Symmetry Propagation outperforms the state-of-the-art static symmetry breaking method Shatter.Keywords
This publication has 14 references indexed in Scilit:
- Enhancing Clause Learning by Symmetry in SAT Solvers2010
- Symmetry and Satisfiability: An Update2010
- Dynamic symmetry-breaking for Boolean satisfiabilityAnnals of Mathematics and Artificial Intelligence, 2009
- Dynamic Symmetry Breaking by Simulating Zykov Contraction2009
- SymChaff: exploiting symmetry in a structure-aware satisfiability solverConstraints, 2008
- Exploiting structure in symmetry detection for CNF2004
- A comparative study of two Boolean formulations of FPGA detailed routing constraintsIEEE Transactions on Computers, 2004
- An Extensible SAT-solver2004
- Shatter2003
- Hard examples for resolutionJournal of the ACM, 1987