The invisible-hand heuristic for origin-destination integer multicommodity network flows

被引：1

作者：

Barr, Richard S. ^{[1
]}

McLoud, Thomas ^{[1
]}

机构：

[1] Southern Methodist Univ, Lyle Sch Engn, Dept Engn Management Informat & Syst, Dallas, TX 75275 USA

来源：

NETWORKS | 2021年 / 78卷 / 04期

关键词：

economics; heuristics; integer programming; logistics; multicommodity; network optimization; telecommunications; BANDWIDTH PACKING; ALGORITHM; BRANCH; PRICE;

D O I：

10.1002/net.22026

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Origin-destination integer multicommodity flow problems differ from classic multicommodity models in that each commodity has one source and one sink, and each commodity must be routed along a single path. A new invisible-hand heuristic that mimics economic markets' behavior is presented and tested on large-scale telecommunications networks, with solution times two orders of magnitude faster than CPLEX's LP relaxation, more dramatic MIP ratios, and small solution value differences.

引用

页码：484 / 502

页数：19

共 35 条

[1]

Ahuja R., 1993, Network flows: theory, algorithms, and applications

[2] SOME RECENT ADVANCES IN NETWORK FLOWS [J].