On primal-dual schema for the minimum satisfiability problem
Date
2016
Authors
Muhammad Arif, Umair
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Abstract
Satisfiability problem is the first problem known to be NP-complete [8, 28]. In this thesis,
we have studied the minimization version of the satisfiability problem called the MINSAT.
Given a set of boolean variables and a set of clauses, such that each clause is a disjunction of variables, the goal is to find the boolean values of the variables so that minimum number of clauses are satisfied. We have used the concept of linear programming and the primal-dual method to study the problem. We have constructed the Linear program of the MINSAT and its restricted version. We have proposed two combinatorial methods to solve the dual of the restricted primal of the MINSAT. Further to this, these two algorithms also obtain an integral solution to the dual of the MINSAT problem. Lastly, we performed a comparison analysis of our proposed algorithms with the simplex method.
Description
Keywords
integral solution , linear programming , MINSAT , primal-dual method