Solving difficult SAT instances in the presence of symmetry

Research in algorithms for Boolean satisfiability and their implementations 23, 6 has recently outpaced benchmarking efforts. Most of the classic DIMACS benchmarks 10 can be solved in seconds on commodity PCs. More recent benchmarks take longer to solve because of their large size, but are still solved in minutes 25. Yet, small and difficult SAT instances must exist because Boolean satisfiability is NP-complete.We propose an improved construction of symmetry-breaking clauses 9 and apply it to achieve significant speed-ups over current state-of-the-art in Boolean satisfiability. Our techniques are formulated as pre-processing and can be applied to any SAT solver without changing its source code. We also show that considerations of symmetry may lead to more efficient reductions to SAT in the routing domain.Our work articulates SAT instances that are unusually difficult for their size, including satisfiable instances derived from routing problems. Using an efficient implementation to solve the graph automorphism problem 18, 20, 22, we show that in structured SAT instances difficulty may be associated with large numbers of symmetries.