Steiner trees and polyhedra

In this paper we study the dominant of the Steiner tree polytope. We introd uce a new class of valid inequalities that generalizes the so-called odd ho le, wheel, bipartite, anti-hole and Steiner partition inequalities introduc ed by Chopra and Rao (Math. Programming 64 (1994) 209-229, 231-246), and we give sufficient conditions for these inequalities to define facets. We des cribe some procedures that permit to construct facets from known ones for t he dominant of the Steiner tree polytope and the closely related Steiner co nnected subgraph polytope. Using these methods we give a counterexample to a conjecture of Chopra and Rao on the dominant of the Steiner tree polytope on 2-trees. We also describe the dominant of the Steiner tree polytope and the Steiner connected subgraph polytope on special classes of graphs. In p articular, we show that if the underlying graph is series-parallel and the terminals satisfy certain conditions, then both polyhedra are given by the trivial inequalities and the Steiner partition inequalities. (C) 2001 Elsev ier Science B.V. All rights reserved.