Pseudo-Boolean Solving by Incremental Translation to SAT

---

Panagiotis Manolios and Vasilis Papavasileiou.
FMCAD, 2011.

Abstract

We revisit pseudo-Boolean Solving via compilation to SAT. We provide an algorithm for solving pseudo-Boolean problems through an incremental translation to SAT that works with any incremental SAT solver as a backend. Experimental evaluation shows that our incremental algorithm solves industrial problems that previous SAT-based approaches do not. We also show that SAT-based algorithms for solving pseudo-Boolean problems should be a part of any portfolio solver.

PDF (128K)