Symmetry propagation: Improved dynamic symmetry breaking in SAT
| Autor: | Christopher Mears, Marc Denecker, Bart Bogaerts, Jo Devriendt, Broes De Cat |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Pure mathematics
Spontaneous symmetry breaking TheoryofComputation_GENERAL Propagator symmetry breaking Satisfiability Symmetry (physics) Constraint Programming Explicit symmetry breaking Theoretical physics Symmetry Constraint programming SAT Symmetry breaking Boolean satisfiability problem Propagation Mathematics |
| Zdroj: | ICTAI |
| Popis: | 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. This is a presentation about the Symmetry Propagation algorithm, given by Chris Mears at the SymCon 2012 conference in Québec City. ispartof: pages:49-56 ispartof: Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'12 vol:1 pages:49-56 ispartof: ICTAI location:Ahtens, Greece date:7 Nov - 9 Nov 2012 status: published |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|