GRASP with path-relinking for the weighted maximum satisfiability problem

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

In Proceedings of IV Workshop on Efficient and Experimental Algorithms (WEA2005), S.E. Nikoletseas (Ed.), Lecture Notes in Computer Science, vol. 3503, pp. 367-379, 2005.


A GRASP with path-relinking for finding good-quality solutions of the weighted 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: 30 March 2005

Copyright Notice