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.
Citation
IBM Research Report RC21846, September 2000.
Article
View Solving Steiner tree problems in graphs with Lagrangian relaxation