Panagiotis (Pete) Manolios
College of Computer and Information Science
Northeastern University

Pseudo-Boolean Solving by Incremental Translation to SAT

Panagiotis Manolios and Vasilis Papavasileiou.
FMCAD, 2011.


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)