Boolean Equi-propagation for Concise and Efficient SAT Encodings of
  Combinatorial Problems
  We present an approach to propagation-based SAT encoding of combinatorial
problems, Boolean equi-propagation, where constraints are modeled as Boolean
functions which propagate information about equalities between Boolean
literals. This information is then applied to simplify the CNF encoding of the
constraints. A key factor is that considering only a small fragment of a
constraint model at one time enables us to apply stronger, and even complete,
reasoning to detect equivalent literals in that fragment. Once detected,
equivalences apply to simplify the entire constraint model and facilitate
further reasoning on other fragments. Equi-propagation in combination with
partial evaluation and constraint simplification provide the foundation for a
powerful approach to SAT-based finite domain constraint solving. We introduce a
tool called BEE (Ben-Gurion Equi-propagation Encoder) based on these ideas and
demonstrate for a variety of benchmarks that our approach leads to a
considerable reduction in the size of CNF encodings and subsequent speed-ups in
SAT solving times.
