Fixed charge multicommodity network design using p-partition facets

Y.K. Agarwal and Y.P. Aneja

European Journal of Operational Research, 2017, vol. 258, issue 1, 124-135

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.

Keywords: Fixed charge; Multicommodity flows; Network design; Integer programming; Polyhedral structure (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716307512
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:258:y:2017:i:1:p:124-135

DOI: 10.1016/j.ejor.2016.09.015

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().