The Steiner tree polytope and related polyhedra

The paper considers the vertex-weighted version of the undirected Steiner tree problem. In this problem, a cost is incurred both for the vertices and the edges present in the Steiner tree. The paper completely describes the associated polytope by linear inequalities when the underlying graph is series-parallel. For general graphs, this formulation can be interpreted as a (partial) extended formulation for the Steiner tree problem. By projecting this formulation, some very large classes of facet-defining valid inequalities are obtained for the Steiner tree polytope.