2012 · 22 citations · 10 references
ComputingComputer ScienceAlgorithmsKnowledge RepresentationOptimizationAutomated ReasoningConstraint ProgrammingConstraint SatisfactionConstraint SolvingSymmetry BreakingBoolean SatisfiabilityConstraint Logic ProgrammingCsp SolvingDynamical Symmetry BreakingPropagation AlgorithmsSatisfiabilityTheory Solvers
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.
10
Efficient Conflict Driven Learning in a Boolean Satisfiability Solver
2001 · 666 citations
Alasdair Urquhart · Journal of the ACM · 1987 · 451 citations · Full text
Efficient conflict driven learning in a Boolean satisfiability solver
Lintao Zhang, C.F. Madigan, M.H. Moskewicz et al. · 2002 · 196 citations
Symmetry breaking in constraint programming
Ian P. Gent, Barbara M. Smith · 2000 · 192 citations
Exploiting structure in symmetry detection for CNF
Paul T. Darga, Mark H. Liffiton, Karem A. Sakallah et al. · 2004 · 156 citations