FACETS FOR POLYHEDRA ARISING IN THE DESIGN OF COMMUNICATION NETWORKS WITH LOW-CONNECTIVITY CONSTRAINTS

被引：50

作者：

Groetschel, Martin ^{[1
]}

Monma, Clyde L. ^{[2
]}

Stoer, Mechthild ^{[1
]}

机构：

[1] Konrad Zuse Zentrum Informat Tech Berlin, D-1000 Berlin 31, Germany

[2] Bell Commun Res Inc, Math Informat Sci & Operat Res, Morristown, NJ 07960 USA

来源：

SIAM JOURNAL ON OPTIMIZATION | 1992年 / 2卷 / 03期

关键词：

network design; network survivability; connectivity; polyhedral combinatorics;

D O I：

10.1137/0802024

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This paper addresses the important practical problem of designing survivable fiber optic communication networks. This problem can be formulated as a minimum-cost network design problem with certain low-connectivity constraints. Previous work presented structural properties of optimal solutions and heuristic methods for obtaining "near-optimal" network designs. Some facetinducing inequalities for the convex hull of the solutions to this problem are given. A companion paper describes computational results on real-world telephone network design problems with a cutting plane method based on this work. These computational results are summarized in the last section of this paper.

引用

页码：474 / 504

页数：31

共 15 条

[1]

BIXBY R. E., 1991, 9032 TR RIC U DEP MA

[2]

CARDWELL R. H., 1988, BELLCORE EXCHANG MAR, P27

[3] COMPUTER-AIDED-DESIGN PROCEDURES FOR SURVIVABLE FIBER OPTIC NETWORKS [J].

CARDWELL, RH ;

MONMA, CL ;

WU, TH .

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 1989, 7 (08) :1188-1197

[4]

Chvatal V., 1973, Discrete Mathematics, V4, P305, DOI 10.1016/0012-365X(73)90167-2

[5]

CORNUEJOLS G., 1988, MATH PROG, V33, P1

[6] MAXIMUM MATCHING AND A POLYHEDRON WITH O'1-VERTICES [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :125-+

[7]

GROTSCHEL M, 1990, SIAM J DISCRETE MATH, V3, P502

[8]

Grotschel M., 1985, TRAVELING SALESMAN P, P251

[9]

GROTSCHEL M., OPER RES IN PRESS

[10]

MAHJOUB AR, 1988, 88520OR U BONN I OP

← 1 2 →