Packing Steiner trees: Further facets (Q1908272)

Let \(G= (V, E)\) be a graph with positive integer capacities \(c_e\) for all \(e\in E\). For a subset \(T\) of \(V\), an edge set \(S\) of \(E\) is called a Steiner tree of \(T\) if for each pair of nodes \(u, v\in T\), \(S\) contains a path between \(u\) and \(v\). Let \(T_1,T_2,\dots, T_n\) be node subsets of \(G\). The Steiner tree packing problem is to find Steiner trees \(S_k\) of \(T_k\) for \(k= 1,2,\dots, n\), such that each edge \(e\in E\) is contained in at most \(c_e S_i\). This paper investigates the Steiner tree packing polyhedron, establishes several new classes of valid inequalities and gives sufficient (and necessary) conditions for these inequalities to be facet-defining. These inequalities can be used to be incorporated into an existing cutting plane algorithm.