COMPUTATIONAL EXPERIENCE WITH A DIFFICULT MIXED-INTEGER MULTICOMMODITY FLOW PROBLEM

被引：47

作者：

BIENSTOCK, D

GUNLUK, O

机构：

[1] Department of Industrial Engineering and Operations Research, Columbia University, New York, 10027, NY

来源：

MATHEMATICAL PROGRAMMING | 1995年 / 68卷 / 02期

关键词：

MIXED-INTEGER PROGRAMMING; MULTICOMMODITY FLOWS;

D O I：

10.1007/BF01585766

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable, We describe computational experience with a cutting plane algorithm for this problem.

引用

页码：213 / 237

页数：25

共 17 条

[1] A DUAL-ASCENT PROCEDURE FOR LARGE-SCALE UNCAPACITATED NETWORK DESIGN
BALAKRISHNAN, A
MAGNANTI, TL
WONG, RT
[J]. OPERATIONS RESEARCH, 1989, 37 (05) : 716 - 740
[2] CERIA S, COMMUNICATION
[3] POLYHEDRA OF THE EQUIVALENT SUBGRAPH PROBLEM AND SOME EDGE CONNECTIVITY PROBLEMS
CHOPRA, S
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (03) : 321 - 337
[4] COOK WR, COMMUNICATION
[5] GRIGORIADIS MD, 1991, DCSTR273 RUTG U DEP
[6] GROTSCHEL M, 1990, SIAM J DISCRETE MATH, V3, P502
[7] GUNLUK O, 1993, THESIS COLUMBIA U
[8] LABOURDETTE JF, 1991, CUCTRTR2449125 COL U
[9] LOGICALLY REARRANGABLE MULTIHOP LIGHTWAVE NETWORKS
LABOURDETTE, JFP
ACAMPORA, AS
[J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1991, 39 (08) : 1223 - 1230
[10] LEIGHTON FT, 1991, 23RD P ANN ACM S THE, P101

← 1 2 →