Design of Survivable Networks Using Three- and Four-Partition Facets

Yogesh Agarwal ()
Additional contact information
Yogesh Agarwal: Indian Institute of Management, Prabandh Nagar, Lucknow 226 013, India

Operations Research, 2013, vol. 61, issue 1, 199-213

Abstract: This paper considers the problem of designing a multicommodity network with single facility type subject to the requirement that under failure of any single edge, the network should permit a feasible flow of all traffic. We study the polyhedral structure of the problem by considering the multigraph obtained by shrinking the nodes, but not the edges, in a k -partition of the original graph. A key theorem is proved according to which a facet of the k -node problem defined on the multigraph resulting from a k -partition is also facet defining for the larger problem under a mild condition. After reviewing the prior work on two-partition inequalities, we develop two classes of three-partition inequalities and a large number of inequality classes based on four-partitions. Proofs of facet-defining status for some of these are provided, while the rest are stated without proof. Computational results show that the addition of three- and four-partition inequalities results in substantial increase in the bound values compared to those possible with two-partition inequalities alone. Problems of 35 nodes and 80 edges with fully dense traffic matrices have been solved optimally within a few minutes of computer time.

Keywords: multicommodity flow; network design; survivability; integer programming; polyhedral structure; facet inequalities; k-partition (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1147 (application/pdf)

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:inm:oropre:v:61:y:2013:i:1:p:199-213

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().