Halaby, M. E.,
*On the Weighted Partial Maximum Satisfiability Problem, *
: Department of Mathematics, Faculty of Science, Cairo University, 2015.

AbstractThis thesis is concerned with the Weighted Partial Maximum Satisfiability problem (WPMax-SAT). The WPMax-SAT problem for a weighted Boolean formula φ = S U H in Conjunctive Normal Form (CNF) is finding an assignment that satisfies all the clauses in H and maximizes the sum of the weights of the satisfied clauses in S. We discuss four aspects of WPMax-SAT. The first is the computational complexity of the problem from the classical and the parametrized perspectives. Secondly, the two solving techniques of WPMax-SAT: branch and bound and SAT-based methods. Third, our experimental investigation on a number of selected solvers. Finally, the applications of WPMax-SAT in real-life.