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

• 成果类型: Article
• 署名作者: Agarwal, Yogesh
• 署名单位: Indian Institute of Management (IIM System); Indian Institute of Management Lucknow
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1147
• 发表日期: 2013
• 页码: 199-213
• 关键词: capacity allocation; path restoration; inequalities; models

摘要

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.