Updated October 15, 2004: most of the codes are now downloadable from the CRIFOR site.
Updated February 18, 2003: the documentation of MCFClass and of all the solvers is now available both in html and pdf formats thanks to doxygen.
MCFClass is an abstract (pure virtual) base C++ class which defines the interface between a generic (single-commodity) (linear) Min Cost Flow (MCF) problem solver and the application programs. The interface tackles basically all needs that an application might have, and provides an abstract layer which make applications independent from the details of the particular solver that is used. A set of "virtualized" data types is used to provide the largest flexibility in choosing the type (integer or floating-point) and the precision of the numbers (costs, flows, indices ...), making it possible to tailor the code to the specific machine and application. A set of compile-time switches is also provided to allow control on some important features without having to bother about their actual implementation.
The attempt here is to set a standard, since we believe it may help faster dissemination and use of results in the field of algorithms for MCF problems, both for research and industrial use. In case you might be interested in developing a MCF algorithm which conforms to the interface, or porting an existing one, a distribution of the MCFClass alone is available. Please let us know of any such development, so that we can list your code together with the ones in this page.
We would also very much appreciate to hear comments about MCFClass. We are painfully aware that the interface is not a tremendously elegant and clean one, especially for its mix of C and C++ styles and the lack of a solid type management. If anybody is willing to contribute to its development, he/she is absolutely welcome. We will probably do something about it in the future, but we believe that the software can already be useful to somebody; that's why we are releasing it now.
The currently available codes that have been developed or ported under the MCFClass interface are:
License: academic license
Version: 1.60
Date: October 15, 2004
MCFZIB
MCFZIB is our C++ porting of the
MCF code by
Andreas Löbel. The code
implements the Primal and Dual Network Simplex algorithm.
License: academic license, or
ZIB
ACADEMIC LICENSE.
Version: 1.21
Date: October 15, 2004
CS2
CS2 is our C++ porting of the
CS2 code by
Andrew Goldberg. The code
implements an efficient Cost-Scaling, Push-Relabel algorithm. Note that the
original code was designed to work with integral costs only; we allow using
float costs also, although the code is not guaranteed to work in this case.
We have extensively tested the code and it has never failed once, but you
should be warned about this.
License: academic license
Version: 1.25
Date: October 15, 2004
License: LGPL
License: LGPL
MCFCplex
MCFCplex is a "wrapper class" which implements a solver conforming to the
MCFClass interface using the Cplex Callable Libraries. The amount of
overhead induced by the extra layer should be relatively small on large MCF
problems, especially if flows and costs are double. This class can be used
as a benchmark for testing and debugging other classes under the MCFClass
interface. Of course, you need to have a Cplex license in order to use this
code.
Version: 1.25
Date: October 15, 2004SPTree
SPTree is a class that solves specially-structured MCF problems that have
in fact a Shortest Path Tree structure, i.e.,
The SPTree class implements a number of classical SPT algorithms assuming
that no negative cycles are present (no check is done) for solving the
associated Shortest Path Tree problem, together with a non-entirely-trivial
visit phase for constructing the optimal flow solution out of the optimal
tree. This class is useful for codes which need to be able to solve generic
MCFs, but may happen to be confronted with problems that are in fact SPTs.
Version: 1.60
Date: October 15, 2004