Solving Steiner tree problems in graphs with Lagrangian relaxation
Laura Bahiense (laurapuc.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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|