To appear in ACM J. on Experimental Algorithmics, 2006.
ABSTRACT
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 PageLast modified: 23 November 2005