A Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals

Matias Siebert, Shabbir Ahmed, George Nemhauser

We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP…