Author:

Keywords:

CSP, SAT, Symmetry, Row symmetry

Abstract:

Symmetry is a topic studied by both the Satisfiability (SAT) and the Constraint Programming (CP) community. However, few attempts at transferring results between both communities have been made. This paper makes the link by investigating how symmetries from Constraint Satisfaction Problems (CSPs) transfer to symmetries of their SAT encodings. We point out that important symmetry groups studied in CP correspond to piecewise row symmetries of their SAT encoding, which -using a CP result- can be broken efficiently. We then show that the standard static symmetry breaking techniques for SAT fail to break these symmetries efficiently, and investigate how this can be mitigated. We also identify the Piecewise Row Interchangeability Detection problem, and we design a first automatic row interchangeability detection scheme for SAT. We implemented hese ideas in the BreakIDGlucose SAT solver, which detects and completely breaks interchangeable row symmetry. BreakIDGlucose’s first place in the hard combinatorial track of the 2013 SAT competition shows the potential of row symmetry exploitation.