Solving the Steiner Tree Problem on a Graph Using Branch and Cut
Sunil Chopra, Edgar R. Gorres, M. R. Rao
ORSA Journal on Computing · 1992 · Volume 4 · Issue 3
Abstract
In this paper we report computational experience with a branch and cut solver for the Steimer tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
Keywords
programming: integer, cutting plane/facet generation, Steiner tree, facets, branch and cut
Enable JavaScript for citation tools and additional paper interactions.