A Scaling Algorithm for Multicommodity Flow Problems

Rina R. Schneur and James B. Orlin
Additional contact information
Rina R. Schneur: PTCG, Inc., Burlington, Massachusetts
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts

Operations Research, 1998, vol. 46, issue 2, 231-246

Abstract: 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 ε-scaling phase, where ε is a function of the penalty and scaling parameters, the algorithm determines an ε-optimal solution; a solution in which complementary slackness conditions are satisfied to within ε. 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.

Keywords: Networks/graphs; multicommodity; new algorithm for problem solving; Analysis of algorithm; computational and theoretical analysis of a scaling algorithm (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.2.231 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:2:p:231-246

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().