Solving the Minimum-Cost Satisfiability Problem Using SAT Based Branch-and-Bound Search

Boolean satisfiability (SAT) has seen many successful applications in various fields, such as electronic design automation (EDA) and artificial intelligence (AI). However, in some cases it may be required/preferable to use variations of the general SAT problem. In this paper we consider one important variation, the minimum-cost satisfiability problem (MinCostSAT). MinCostSAT is a SAT problem which minimizes the cost of the satisfying assignment. MinCostSAT has various applications, e.g. automatic test pattern generation (ATPG), FPGA routing, AI planning, etc. This problem has been tackled before - first by covering algorithms, e.g. scherzo (Coudert, 1996), and more recently by SAT based algorithms, e.g. bsolo (Manquinho and Marques-Silva, 2002). However the SAT algorithms they are based on are not the current generation of highly efficient solvers. The solvers in this generation, e.g. Chaff (Moskewicz et al., 2001), MiniSat (Een and Sorensson, 2006) etc., incorporate several new advances, e.g. two literal watching based Boolean Constraint Propagation, that have delivered order of magnitude speedups. We first point out the challenges in using this class of solvers for the MinCostSAT problem and then present techniques to overcome these challenges. The resulting solver MinCostChaff shows order of magnitude improvement over several current best known branch-and-bound solvers for a large class of problems, ranging from minimum test pattern generation, bounded model checking in EDA to graph coloring and planning in AI