Strong inequalities for capacitated survivable network design problems

被引：35

作者：

Bienstock, D ^{[1
]}

Muratore, G ^{[1
]}

机构：

[1] Columbia Univ, New York, NY 10027 USA

来源：

MATHEMATICAL PROGRAMMING | 2000年 / 89卷 / 01期

关键词：

D O I：

10.1007/PL00011390

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present several classes of facet-defining inequalities to strengthen polyhedra arising as subsystems of network design problems with survivability constraints. These problems typically involve assigning capacities to a network with multicommodity demands, such that after a vertex- or edge-deletion at least some prescribed fraction of each demand can be routed.

引用

页码：127 / 147

页数：21

共 21 条

[1] Survivable mobile phone network architectures: Models and solution methods
Alevras, D
Grotschel, M
Jonas, P
Paul, U
Wessaly, R
[J]. IEEE COMMUNICATIONS MAGAZINE, 1998, 36 (03) : 88 - 93
[2] ALEVRAS D, 1997, CAPACITY SURVIVABILI
[3] ALEVRAS D, 1988, ANN OPER RES, V76, P1
[4] BALAKRISHNAN A, 1997, MODELING SOLVING SIN
[5] Network design using cut inequalities
Barahona, F
[J]. SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (03) : 823 - 837
[6] Minimum cost capacity installation for multicommodity network flows
Bienstock, D
Chopra, S
Gunluk, O
Tsai, CY
[J]. MATHEMATICAL PROGRAMMING, 1998, 81 (02) : 177 - 199
[7] Bienstock D., 1996, INFORMS Journal on Computing, V8, P243, DOI 10.1287/ijoc.8.3.243
[8] BIENSTOCK D, 1997, ATM NETWORK DESIGN T
[9] BRIGHTWELL G, 1996, LSECDAM962 CDAM
[10] FACETS FOR POLYHEDRA ARISING IN THE DESIGN OF COMMUNICATION NETWORKS WITH LOW-CONNECTIVITY CONSTRAINTS
Groetschel, Martin
Monma, Clyde L.
Stoer, Mechthild
[J]. SIAM JOURNAL ON OPTIMIZATION, 1992, 2 (03) : 474 - 504

← 1 2 3 →