**1998 October 09**

The program `MCMCF` approximately solves the minimum-cost
multicommodity flow problems on directed graphs. For information
about this problem, read the technical reports on the author's home
page
http://theory.stanford.edu/~oldham
or in *Network Flows* [AMO93].
The sections below show show how to run the program, the input and
output formats, and known restrictions.

To invoke `MCMCF`, use a command line like

The results are sent to the standard output.

The program's execution can be altered using command-line flags. Some of these flags include:

-E epsilon |
overrides the desired program accuracy value specified in the input. |

-L minimum- |
indicates a lower bound on , i.e., the multiple of the arc capacities needed to satisfy the the demands. The program terminates when is within a factor 1 + of the specified value and the costs are within the same factor of the minimum possible costs. For the minimum-cost multicommodity flow problem, the default is 1.0 . That is, stop when the flow fits within a network using at most 1 + times arc capacity (and has small enough cost). |

-l frequency |
indicates the number of iterations (as a multiple of the number of commodities) that should occur between calculation of the lower bound. The default value is 3. |

-t multiple |
helps the program find an initial solution. By default, the program attempts to find an initial solution by individually routing each commodity through the network with capacities as specified in the input. Using the flag, causes the program to trying routing the commodities through a network with capacities multiplied by the specified floating point number. If the problem can be solved with 1 , this flag should not be necessary. |

For example, to solve a problem with 4% accuracy when the input specifies an accuracy of 10%, use

The multicommodity flow format is an extension of the DIMACS Algorithm Implementation Challenge network flow formats [DIM91]. Each line of a problem specification (input) or multicommodity flow (output) starts with a unique, lowercase identifying letter.

**Comments.**- A comment begins with a lowercase
`c`and ends at the end of the line.

`c This is an example of a comment line.`

**Problem descriptor.**`One problem descriptor line must appear exactly once before any arc or commodity lines.`

`p mcmcf`*nodes**arcs**commodities*

The integerspecifies the number*nodes**n*of nodes in the graph. The integersand*arcs*specify the numbers*commodities**m*and*k*of arcs and commodities, respectively.**Arc descriptors.**`For each arc, there is exactly one arc descriptor line.`

`a`*src**dst**cap**cost*

The arc (,*src*) has capacity*dst*and cost*cap*. Nodes*cost*and*src*must have integral values in the range [1,*dst**n*] . Capacities and costs are nonnegative floating point numbers. The number of arc descriptors must matchin the problem descriptor.*arcs***Commodity descriptors.**`For each commodity, there is exactly one commodity descriptor line.`

`k`*src**dst**demand*units of flow must travel from node*demand*to node*src*. The nodes*dst*and*src*must have integral values in the range [1,*dst**n*] , while the demand may be any nonnegative floating point number. The number of commodity descriptors must matchin the problem descriptor.*commodities***Precision descriptor.**`Exactly one line specifying the desired approximation must appear.`

`e`*epsilon*

The desired approximationmust be a positive floating point number.*epsilon*

The result of executing `MCMCF` on a problem is a file with
the following format:

**Comments.**- A comment begins with a lowercase
`c`and ends at the end of the line.

`c This is an example of a comment line.`

**Solution line.**`The approximate minimum-cost of the multicommodity flow appears in this line.`

`s`*solution*

**Flow descriptors.**`For each arc and commodity, one line`

`f`*src**dst**commodity**flow*

specifies the flow of commodityfrom node*commodity*to node*src*.*dst*

`MCMCF` is a research tool and is still in development.
Thus, we provide no guarantee about its behavior. The program has the
following known restrictions. If you experience other difficulties,
please contact the author
.

- 1.
- The program solves the single-source, single-sink directed
multicommodity flow problem. Internally,
`MCMCF`groups commodities with the same source nodes. The output is for these grouped nodes. The author can construct a Perl script to convert these flows to correspond to the original commodities. - 2.
- The program solves directed multicommodity flow problems. The author can provide a script to convert undirected problems to directed ones. With sufficient motivation, the author can modify the program internals to support directly undirected problems.
- 3.
- For large accuracies, e.g., accuracy < 0.2% , the Newton-Raphson method may enter an infinite loop because of precision problems.
- 4.
- Be sure to specify a lower bound on the permissible
using the
`-L`option. - 5.
- Parallel arcs with the same tail and head nodes are not supported.
- 6.
- The arc costs and capacities are the same for all commodities. Each commodity must have a distinct pair of source and destination vertices.
- 7.
- If too high a precision is desired, e.g., 0.1%, the program may attempt to exponentiate a very large number and fail.

**AMO93**-
Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.
*Network Flows: Theory, Algorithms, and Applications*.

Prentice Hall, Englewood Cliffs, NJ, 1993. **DIM91**-
The first dimacs international algorithm implementation challenge: Problem
definitions and specifications.
`ftp://dimacs.rutgers.edu/pub/netflow/general-info/specs.{tex,bbl}`, 1991.

- ...Problems
^{1} - ©1998 Jeffrey D. Oldham . All rights reserved. This document may not be redistributed in any form without the express permission of the author.