Premium
A lower bound for the steiner tree problem in directed graphs
Author(s) -
Liu Weiguo
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200606
Subject(s) - steiner tree problem , combinatorics , mathematics , upper and lower bounds , polyhedron , integer programming , ball (mathematics) , tree (set theory) , discrete mathematics , mathematical optimization , mathematical analysis
Abstract In this article, we introduce a new integer programming formulation for the minimum Steiner tree problem in directed graphs. With the observation that every Steiner tree contains a two‐terminal Steiner tree for every pair of the terminals, our formulation is based on the linear programming formulation for the two terminal Steiner tree polyhedron obtained by Ball et al. [2]. By the results of Ball et al. [2], this formulation contains a large class of facets that are different from those induced by the well‐known Steiner cut constraints. We give a general form of the dual ascent algorithm and discuss the relationship between this algorithm and the projection method for extended formulations. This dual ascent algorithm is applied to the new formulation to obtain a lower bound for the minimum Steiner tree problem. In the algorithm, we use the dual ascent algorithm introduced by Wong [16] as a subroutine and improve his lower bound. Some computational results are given in Section 3.