GRASP with path-relinking for the weighted MAXSAT problem

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

To appear in ACM J. on Experimental Algorithmics 2006.


A GRASP with path-relinking for finding good-quality solutions of the weight\-ed maximum satisfiability problem (MAX-SAT) is described in this paper.  GRASP, or Greedy Randomized Adaptive Search Procedure, is a randomized multi-start metaheuristic, where at each iteration locally optimal solutions are constructed, each independent of the others.  Previous experimental results indicate its effectiveness for solving weighted MAX-SAT instances. Path-relinking is a procedure used to intensify the search around good-quality isolated solutions that have been produced by the GRASP heuristic.  Experimental comparison of the pure GRASP (without path-relinking) and the GRASP with path-relinking illustrates the effectiveness of  path-relinking in decreasing the average time needed to find a good-quality solution for the weighted maximum satisfiability problem.

PDF file of full paper

Mauricio G.C. Resende's Home Page
Last modified: 23 November 2005

Copyright Notice