The MCFClass Project


September 25, 2013: Johannes Sommer has released pyMCFSimplex, a Python Wrapper for MCFSimplex. Check his blog for details and to download the code. I can only say "thanks!"

September 15, 2011: a new distribution for all solvers, as well as an entirely new solver, is now available under a slightly modified and improved version of the interface. All current solvers are now available for download locally, while previous version are still available from the CRIFOR site.

October 15, 2004: most of the codes are now downloadable from the CRIFOR site.

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 defined and "exported" by the base class 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. Caveats exist for individual solvers, so be sure to read the documentation if you need to play with these.

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 current version of MCFClass alone is available; the previous version can still be found at the CRIFOR site. 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:


MCFClass

MCFClass is just the header file MCFClass.h defining the base class, some small auxiliary header files and the Doxygen documentation.

License: LGPL
First release 1996. Current version: 3.01, February 11, 2011
Authors: Alessandro Bertolini, Antonio Frangioni, Claudio Gentile

MCFClass


RelaxIV

RelaxIV is our C++ re-implementation of the Relaxation algorithm by D. Bertsekas, based on his original Fortran code. The code seems to work fairly well as a general-purpose MCF solver, and it is apparently capable of dealing with problems with nonintegral costs and/or capacities, although you have to be warned that Relaxation algorithms may in theory fail to converge with nonintegral data.

License: academic license
First release 1996. Current version: 1.80, February 11, 2011
Authors: Dimitri P. Bertsekas, Antonio Frangioni, Claudio Gentile

Ask for it (no direct download as the license need be explicitly accepted)


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.
First release 1997. Current version: 1.30, February 11, 2011
Authors: Andreas Loebel, Antonio Frangioni, Antonio Manca

Ask for it (no direct download as the license need be explicitly accepted)


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
First release 1997. Current version: 1.40, February 11, 2011
Authors: Andrew Goldberg, Antonio Frangioni, Antonio Manca

Ask for it (no direct download as the license need be explicitly accepted)


MCFCplex

MCFCplex is a "wrapper class" which implements a solver conforming to the MCFClass interface using the IBM ILOG 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 (but Cplex licenses are free now, at least for academics).

License: LGPL
First release 1997. Current version: 1.40, February 11, 2011
Authors: Antonio Frangioni, Antonio Manca, Matteo Sammartino

Download


SPTree

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. This is not an even remotely competitive implementation for large-scale SPT problems, and in particular it does nothing to efficiently re-optimize when the data of the problem changes, although the MCFClass interface would allow it. Yet, even this relatively dumb implementation of SPT is usually much faster than proper MCF codes at solving SPT problems, that's why such a class occasionally makes sense.

License: LGPL
First release 1996. Current version: 1.80, February 11, 2011
Author: Antonio Frangioni

Download


MCFSimplex

MCFSimplex is our freshly-developed implementation of the primal and dual network simplex algorithm for MCF problems. Its strong points are:

It is also reasonably efficient when compared to most other available network simplex codes.

License: LGPL
First release 2008. Current version: 1.00, August 29, 2011
Author: Alessandro Bertolini, Antonio Frangioni

Download