Minimum-Cost Multicommodity Flows

Jeffrey D. Oldham
Computer Science Department
Stanford University
oldham@cs.stanford.edu
http://theory.stanford.edu/~oldham

1997 November 18

The minimum-cost multicommodity flow problem simultaneously ships multiple commodities through a single network so the total flow obeys the arc capacity constraints and has minimum cost. For example, in telephone networks, calls between different locations must be routed through the same telephone cables which have finite capacities and differing costs.

The program MCMCF solves the minimum-cost multicommodity flow problem using gradient optimization and theoretically efficient algorithms. In practice, the implementation is two to three orders of magnitude faster than linear-programming based implementations.

MCMCF produces an approximate solution in that, given accuracy parameter  $\epsilon$ , it produces an $\epsilon$ -optimal flow that uses at most 1 + $\epsilon$  times the arc capacities and which costs at most 1 + $\epsilon$  times the minimum possible cost. In practice, it is often sufficient to find approximate multicommodity flow solutions (e.g., within 1% of the optimal), rather than an exact ones.

We compare MCMCF to two of the fastest known linear-programming implementations CPLEX and PPRN, both of which compute exact solutions. On the examples we studied, our combinatorial program found solutions several orders of magnitude faster than the above codes took to find exact solutions. For example, for 1% accuracy, MCMCF is up to one thousand times faster than both CPLEX and PPRN. Furthermore, our implementation exhibits less dependence on the number  k of commodities and the network size. Thus, much larger problem instances can now be solved.

Joint work with Andrew Goldberg, Serge Plotkin, and Cliff Stein.