Some formulations for the group steiner tree problem

The group Steiner tree problem consists of, given a graph G  , a collection RR of subsets of V(G)V(G) and a cost c(e)c(e) for each edge of G  , finding a minimum-cost subtree that connects at least one vertex from each R∈RR∈R. It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.