Optimization Online


Solving Steiner tree problems in graphs with Lagrangian relaxation

Laura Bahiense (laura***at***puc.br)
Francisco Barahona (barahon***at***us.ibm.com)
Oscar Porto (oscar***at***puc.br)

Abstract: This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lowe r bounds and to estimate primal solutions. Due to the high quality of the bounds, it was possible to solve many difficult instances from the literature to proven optimality, without preprocessing or branching. Computational results are reported for many problems drawn from the literature, including those in the SteinLib library.

Keywords: Steiner tree, lagrangian relaxation, volume algorithm

Category 1: Combinatorial Optimization (Graphs and Matroids )

Citation: IBM Research Report RC21846, September 2000.

Download: [Compressed Postscript]

Entry Submitted: 02/01/2001
Entry Accepted: 02/01/2001
Entry Last Modified: 10/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