Paper Info
Title
GRASP with path-relinking for the weighted maximum satisfiability problem
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.
Year
DOI
Venue
2005
10.1007/11427186_32
WEA
Keywords
Field
DocType
weighted maximum satisfiability problem,pure grasp,grasp heuristic,greedy randomized adaptive search,experimental comparison,previous experimental result,good-quality solution,weighted max-sat instance,average time,good-quality isolated solution,greedy randomized adaptive search procedure,satisfiability
Maximum satisfiability problem,Heuristic,Mathematical optimization,Algorithmics,GRASP,Adaptive method,Computer science,Boolean satisfiability problem,Algorithm,Greedy randomized adaptive search procedure,Metaheuristic
Conference
Volume
ISSN
ISBN
3503
0302-9743
3-540-25920-1
Citations 
PageRank 
References 
3
0.48
22
Authors
4
Name
Order
Citations
PageRank
Paola Festa128725.32
Panos M. Pardalos23720397.84
Leonidas S. Pitsoulis317022.11
Mauricio G. C. Resende43729336.98