Optimization Online


Nonmonotone GRASP

M. De Santis (msantis***at***math.tu-dortmund.de)
P. Festa (paola.festa***at***unina.it)
G. Liuzzi (liuzzi***at***iasi.cnr.it)
S. Lucidi (lucidi***at***dis.uniroma1.it)
F. Rinaldi (rinaldi***at***math.unipd.it)

Abstract: A Greedy Randomized Adaptive Search Procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as new current solution. In this paper, we propose a variant of the GRASP framework that uses a new nonmonotone strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on the Maximum Cut Problem, a classical hard combinatorial optimization problem.

Keywords: Combinatorial Optimization, GRASP, Metaheuristics, Local Search, Nonmonotone Line Search, MAX-CUT

Category 1: Combinatorial Optimization (Meta Heuristics )


Download: [PDF]

Entry Submitted: 02/27/2014
Entry Accepted: 02/28/2014
Entry Last Modified: 06/25/2015

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 Optimization Society