Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation |
| |
| Authors: | Laura Bahiense Francisco Barahona Oscar Porto |
| |
| Institution: | (1) Universidade Federal do Rio de Janeiro, COPPE-Sistemas e Computação, P.O. Box 68511, Rio de Janeiro, RJ, 21945-970, Brazil;(2) IBM T. J. Watson Research Center, Yorktown Heights, NY 10589, USA;(3) PUC-Rio, Dept. de Engenharia Elêtrica, Rua Marquês de São Vicente 225, Predio Cardeal Leme, Sala 401, CEP 22453-900 Rio de Janeiro, RJ, Brazil |
| |
| 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 lower bounds and to estimate primal solutions. It was possible to solve several difficult instances from the literature to proven optimality without branching. Computational results are reported for problems drawn from the SteinLib library. |
| |
| Keywords: | Steiner trees Lagrangian relaxation |
| 本文献已被 SpringerLink 等数据库收录！ |
|
