Thumbnail
Access Restriction
Subscribed

Author Festa, Paola ♦ Pardalos, Panos M. ♦ Pitsoulis, Leonidas S. ♦ Resende, Mauricio G C
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Algorithms ♦ GRASP ♦ Experimentation ♦ Heuristics ♦ Path relinking ♦ Performance ♦ Time-to-target plots
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 multistart 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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-02-09
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 11


Open content in new tab

   Open content in new tab
Source: ACM Digital Library