Approximate Solution of Weighted MAX-SAT Problems using GRASP

Mauricio G.C. Resende, L. S. Pitsoulis, and P. M. Pardalos

In The Satisfiability Problem: Theory and Applications, D.-Z. Du, J. Gu, and P.M. Pardalos, eds., DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 35, pp. 393-405, 1997.


Computing the optimal solution to an instance of the weighted maximum satisfiability problem (MAX-SAT) is difficult even when each clause contains at most two literals.  In this paper, we describe a greedy randomized adaptive search procedure (GRASP) for computing approximate solutions of weighted MAX-SAT problems.  The heuristic is tested on a large set of test instances.  Computational experience indicates the suitability of GRASP for this class of problems.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 25 June 2002

Copyright Notice