A scaling algorithm for multicommodity flow problems
成果类型：
Article
署名作者：
Schneur, RR; Orlin, JB
署名单位：
Massachusetts Institute of Technology (MIT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.2.231
发表日期：
1998
页码：
231-246
关键词：
摘要：
We present a penalty-based algorithm that solves the multicommodity flow problem as a sequence of a finite number of scaling phases. The basis of the algorithm is simple and consists of iteratively detecting and sending flow around negative cost cycles. Two parameters control the algorithm's behavior: the penalty parameter and the scaling parameter. In the epsilon-scaling phase, where epsilon is a function of the penalty and scaling parameters, the algorithm determines an E-optimal solution; a solution in which complementary slackness conditions are satisfied to within epsilon. We analyze the performance of the algorithm from both the theoretical and practical perspectives. The computational results support the theoretical behavior of the algorithm. They also demonstrate the efficiency of the algorithm for solving problem instances of different structure and size.