Institution: Stanford University, Department of Computer Science

Title: An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow

Author: Goldberg, Andrew

Author: Oldham, Jeffrey D.

Author: Plotkin, Serge

Author: Stein, Cliff

Date: December 1997

Abstract: The minimum-cost multicommodity flow problem involves simultaneously shipping multiple commodities through a single network so that the total flow obeys arc capacity constraints and has minimum cost. Multicommodity flow problems can be expressed as linear programs, and most theoretical and practical algorithms use linear-programming algorithms specialized for the problems' structures. Combinatorial approximation algorithms yield flows with costs slightly larger than the minimum cost and use capacities slightly larger than the given capacities. Theoretically, the running times of these algorithms are much less than that of linear-programming-based algorithms. We combine and modify the theoretical ideas in these approximation algorithms to yield a fast, practical implementation solving the minimum-cost multicommodity flow problem. Experimentally, the algorithm solved our problem instances (to 1% accuracy) two to three orders of magnitude faster than the linear-programming package CPLEX and the linear-programming based multicommodity flow program PPRN.

http://i.stanford.edu/pub/cstr/reports/cs/tr/97/1600/CS-TR-97-1600.pdf