Solving Steiner tree problems in graphs with Lagrangian relaxation

Laura Bahiense (laurapuc.br)
Francisco Barahona (barahonus.ibm.com)
Oscar Porto (oscarpuc.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