Fixed charge multicommodity network design using p-partition facets

We are given an undirected network G[V, E] and a set of traffic demands. To install a potential edge e ∈ E we incur a cost Fe to provide a positive capacity ae. The objective is to select edges, at minimum cost, so as to permit a feasible multicommodity flow of all traffic. We study structure of the projection polytope of this problem, in the space of binary variables associated with fixed-charges, by relating facets of a p node problem (p=2,3, or 4), defined over a multi-graph obtained by a p-partition of V, to the facets of the original problem. Inspired from the well-known “cover” inequalities of the Knapsack Problem, we develop the notion of p-partition cover inequalities. We present necessary and sufficient conditions for such inequalities to be facet defining for p = 3 and 4. A simple heuristic approach for separating and adding such violated inequalities is presented, and implemented for p values up to 10. We report optimal solutions for problems with 30 nodes, 60 edges, and fully dense demand matrices within a few minutes of cpu time for most instances. Some results for dense graph problems are also reported.