GRASP with path-relinking for the weighted maximum satisfiability problem

Paola Festa (paola.festaunina.it)
Panos M. Pardalos (pardalosufl.edu)
Leonidas S. Pitsoulis (pitsouligen.auth.gr)
Mauricio G. C. Resende (mgcrresearch.att.com)

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.

Keywords: GRASP, path-relinking, satisfiability, logic

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Global Optimization (Stochastic Approaches )

Citation: AT&T Labs Research Technical Report TD-68QNGR, January 17, 2005.

Download: [PDF]

Entry Submitted: 01/17/2005
Entry Accepted: 01/18/2005
Entry Last Modified: 01/17/2005

Modify/Update this entry