Optimization Online


GRASP with path-relinking for the weighted maximum satisfiability problem

Paola Festa (paola.festa***at***unina.it)
Panos M. Pardalos (pardalos***at***ufl.edu)
Leonidas S. Pitsoulis (pitsouli***at***gen.auth.gr)
Mauricio G. C. Resende (mgcr***at***research.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society