TítolSolving (Weighted) Partial MaxSAT Through Satisfiability Testing
Publication TypeConference Paper
Year of Publication2009
AuthorsAnsótegui C, Bonet MLuisa, Levy J
EditorKullmann O.
Conference NameProc. of the 20th Int. Conf. on Theory and Applications of Satisfiability Testing, SAT'09
Volume5584
EditorSpringer-Verlag
Paginació427-440
Resum

Recently, Fu and Malik described an unweighted Partial MaxSAT solver based on successive calls to a SAT solver. At the kth 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.