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 , it produces an * -optimal
flow* that uses at most 1 + times the arc capacities and
which costs at most 1 + 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.