Dynamic Symmetry Breaking in SAT using Augmented Clauses with a Polynomial-Time Lexicographic Pruning
Tevich Treethanyaphong, Athasit Surarerks · 2018 2nd European Conference on Electrical Engineering and Computer Science (EECS) · 2018
Dynamic symmetry breaking in Boolean satisfiability problems (SAT) is often performed by adding symmetric versions of the learned clauses into the clause database. Using a notion of augmented clause every symmetric version can be learned. The task of unit propagation is then transformed into a search problem under a permutation group. Our work focuses on a special kind of symmetry called row symmetry. We present the optimization to the search problem under a group containing row symmetry subgroups mainly relies on lexicographic pruning and the fact that some instances can be reduced to minimal assignment problems. We also introduce a construction of subgroups of row symmetry groups to ensure that every sub-task could be performed in polynomial time. Lastly, we discuss the implementation of our technique and some of the technical issue that needed to be address.