Optimization Online


A Hybrid GRASP with Perturbations for the Steiner Problem in Graphs

Celso Ribeiro (celso***at***inf.puc-rio.br)
Eduardo Uchoa (uchoa***at***inf.puc-rio.br)
Renato Werneck (rwerneck***at***inf.puc-rio.br)

Abstract: We propose and describe a hybrid GRASP with weight perturbations and adaptive path-relinking heuristic (HGP+PR) for the Steiner problem in graphs. In this multi-start approach, the greedy randomized construction phase of a GRASP is replaced by the use of several construction heuristics with a weight perturbation strategy that combines intensification and diversification elements, as in a strategic oscillation approach. The improvement phase circularly explores two different local search strategies. The first uses a node-based neighborhood for local search, while the second uses a key-path-based neighborhood. An adaptive path-relinking technique is applied to a set of elite solutions as a post-optimization strategy. Computational results on a broad set of benchmark problems illustrate the effectiveness and the robustness of our heuristic, which is very competitive when compared to other approximate algorithms.

Keywords: Steiner problem in graphs, metaheuristics, GRASP, perturbations, path-relinking

Category 1: Combinatorial Optimization (Meta Heuristics )

Category 2: Applications -- Science and Engineering (VLSI layout )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: Revised version submitted for publication, May 2001, Department of Computer Science, Catholic University of Rio de Janeiro, Rua Marquês de São Vicente 225, Rio de Janeiro 22453-900, Brazil

Download: [Postscript][Compressed Postscript]

Entry Submitted: 05/03/2001
Entry Accepted: 05/03/2001
Entry Last Modified: 05/03/2001

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