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 [J].