Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation

Laura Bahiense (), Francisco Barahona () and Oscar Porto ()
Additional contact information
Laura Bahiense: Universidade Federal do Rio de Janeiro, COPPE-Sistemas e Computação
Francisco Barahona: IBM T. J. Watson Research Center
Oscar Porto: Rua Marquês de São Vicente 225, Predio Cardeal Leme, Sala 401

Journal of Combinatorial Optimization, 2003, vol. 7, issue 3, No 5, 259-282

Abstract: 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 (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1027368621279 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:7:y:2003:i:3:d:10.1023_a:1027368621279

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1027368621279

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().