Application of Hierarchical Hybrid Encodings to Efficient Translation of CSPs to SAT

Solving Constraint Satisfaction Problems (CSPs) by Boolean Satisfiability (SAT) requires suitable encodings for translating CSPs to equivalent SAT instances that can not only be efficiently generated, but also efficiently processed by SAT solvers. In this paper we investigate hierarchical and hybrid encodings, namely a previously proposed log-direct encoding, as well as a new combination, the log-order encoding. Experiments conducted on different domain problems with these hierarchical encodings demonstrate their significant promise in practice ... the log-direct encoding significantly outperforms the direct encoding (typically by one or two orders of magnitude) ... the log-order encoding is clearly competitive with the order encoding although more studies are required to clearly understand the tradeoff between the fewer variables and longer clauses in the former when expressing complex CSP constraints.