Polyhedral Structure of the 4-Node Network Design Problem

被引:5
作者
Agarwal, Yogesh K. [1 ]
机构
[1] Indian Inst Management, Decis Sci Grp, Lucknow 226013, Uttar Pradesh, India
关键词
facet inequality; multicommodity; network design; integer programming; polyhedral structure; k-partition; CONNECTIVITY CONSTRAINTS; MULTICOMMODITY FLOWS; LOADING PROBLEM; INEQUALITIES; ALGORITHM;
D O I
10.1002/net.20317
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
This article studies the polyhedral structure of the 4-node network design problem (NDP). Using a theorem from the previous work of this author, the facets of the 4-node NDP can be translated into facets of larger size problems. The knowledge of complete polyhedral description of the 4-node NDP is important because it implies complete knowledge of 4-partition-based facets of larger NDPs. After reviewing the previously known facets of the 4-node NDP, a new class of facets is derived. An enumerative methodology is presented for determining whether a given set of inequalities provides a complete polyhedral description. By implementing this methodology in a computer code, it is determined that the known facets of the 4-node NDP indeed provide a complete polyhedral description of the problem. Working of the proof methodology is illustrated with examples, and the results of the computer enumeration are reported. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 54(3),139-149 2009
引用
收藏
页码:139 / 149
页数:11
相关论文
共 24 条
  • [1] k-Partition-based facets of the network design problem
    Agarwal, YK
    [J]. NETWORKS, 2006, 47 (03) : 123 - 139
  • [2] AGARWAL YK, 1998, 199810 IIM
  • [3] AGARWAL YK, 1999, 9906 IIM
  • [4] Metric inequalities and the Network Loading Problem
    Avella, Pasquale
    Mattia, Sara
    Sassano, Antonio
    [J]. DISCRETE OPTIMIZATION, 2007, 4 (01) : 103 - 114
  • [5] Telecommunication link restoration planning with multiple facility types
    Balakrishnan, A
    Magnanti, TL
    Sokol, JS
    Wang, Y
    [J]. ANNALS OF OPERATIONS RESEARCH, 2001, 106 (1-4) : 127 - 154
  • [6] Network design using cut inequalities
    Barahona, F
    [J]. SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (03) : 823 - 837
  • [7] Strong inequalities for capacitated survivable network design problems
    Bienstock, D
    Muratore, G
    [J]. MATHEMATICAL PROGRAMMING, 2000, 89 (01) : 127 - 147
  • [8] Minimum cost capacity installation for multicommodity network flows
    Bienstock, D
    Chopra, S
    Gunluk, O
    Tsai, CY
    [J]. MATHEMATICAL PROGRAMMING, 1998, 81 (02) : 177 - 199
  • [9] Bienstock D., 1996, INFORMS Journal on Computing, V8, P243, DOI 10.1287/ijoc.8.3.243
  • [10] Dahl G., 1998, INFORMS Journal on Computing, V10, P1, DOI 10.1287/ijoc.10.1.1