Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959955 | European Journal of Operational Research | 2017 | 12 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Y.K. Agarwal, Y.P. Aneja,