A branch and cut algorithm for the Steiner problem in graphs (with A. Lucena), Networks, vol.31, 1998, pp39-59
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 non-negative 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.