Solving (Weighted) Partial MaxSAT through Satisfiability Testing

Abstract Recently, Fu and Malik described an unweighted Partial MaxSAT solver based on successive calls to a SAT solver. At the k th iteration the SAT solver tries to certify that there exist an assignment that satisfies all but k clauses. Later Marques-Silva and Planes implemented and extended these ideas. In this paper we present and implement two Partial MaxSAT solvers and the weighted variant of one of them. Both are based on Fu and Malik ideas. We prove the correctness of our algorithm and compare our solver with other (Weighted) MaxSAT and (Weighted) Partial MaxSAT solvers.

Authors

• Carlos Ansótegui
• Maria Luisa Bonet
• Jordi Levy

Keywords

No keywords are indexed for this paper.