flow deviation

FLOW DEVIATION METHOD

This package approximately solves the maximum throughput routing problem. This problem is equivalent to the minimum congestion routing problem, and collectively they are known as the "maximum concurrent flow problem".

For complete references, see: D. Bienstock and O. Raskina, "Asymptotic Analysis of the Flow Deviation Method for the Maximum Concurrent Flow Problem" , Math. Programming 91 (2002), 479 - 492.

This is an initial, "one-off" implementation which has nonetheless proven effective. Future versions will be posted as they become available.

Upon termination, the code has a solution whose throughput is proved to be of the stated accuracy. Typically the solution is achieved long before the code actually produces the proof.

This package requires the use of Cplex 7.1 or later.

As downloaded, the package should compile with no warnings on a (recent) Linux system. It also compiles and runs correctly on other Unix platforms, but this will require some small changes to the makefile.

On very large problems, the package requires approximately one-third of the memory that the Cplex dual simplex method requires. The package (of course) aggregates commodities by source. Nonetheless, a very large problem instance may still require a nontrivial amount of memory -- in order to store a Cplex "LP" data structure for each commodity. In the event that the package requires too much memory for your system, use the "-o" command-line option, which saves the Cplex LPs to disk.

After compilation, you will have a binary named fd. To run the program, use a command of the form: fd -i input.dat

Here, "input.dat" is a data file containing both the network and the (point-to-point) commodities in fluff-free "dimacs" format. Here is a small sample data file. The first line contains the number of nodes, arcs and commodities. Each line starting with " a" describes an arc (tail, head, capacity, followed by a zero). Each line starting with "k" describes a commodity (source, destination, amount). An "END" at the end of the file is required.

Running fd on this data file will produce this log file. A typical line of output will look like:

o 11 i 0 r 16 (g 1.296e-02 [ 1.304e-02 ] l 9.940e-01 b 6.959e+02) t 8.030e+01

Here the quantity in square brackets indicates the current throughput, the number following "t" is the running time, and the integer following the "r" is the number of minimum-cost flow problems that have been solved so far.

Proceed to the download page

This work was supported by NSF award 9527124.