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.
ABSTRACT
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 PageLast modified: 30 March 2005