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.
ABSTRACT
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.