Article ID: | iaor20022458 |
Country: | United States |
Volume: | 31 |
Issue: | 1 |
Start Page Number: | 39 |
End Page Number: | 59 |
Publication Date: | Jan 1998 |
Journal: | Networks |
Authors: | Beasley J.E., Lucena A. |
Keywords: | Steiner problem |
In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraints given previously in the literature. We strengthen this SST formulation and present a branch and cut algorithm to solve the problem to optimality. This algorithm incorporates reduction tests and is used to solve a number of problems drawn from the literature. A number of general issues relating to branch and cut algorithms are also highlighted.