The MCFClass Project

April 14, 2019: Having obtained explicit permission from Dimitri P. Bertsekas, RelaxIV is now also available directly from the GitHub repository, although still under the less permissive Academic License instead of the LGPL 3.0 under which the rest of the code is distributed.

April 25, 2017: The LGPL part of the MCFClass project has been moved to a GitHub repository, see below.

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. 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:


RelaxIV is our C++ re-implementation of the Relaxation algorithm by D. Bertsekas, based on his original RELAXIV Fortran code described in
Bertsekas, Dimitri P., and Paul Tseng. "RELAX-IV: A faster version of the RELAX code for solving minimum cost flow problems." (1994), Report LIDS-P-2276, MIT.
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
Authors: Dimitri P. Bertsekas and Paul Tseng (original FORTRAN code), Antonio Frangioni and Claudio Gentile (C++ porting and polishing)



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
Authors: Andreas Loebel, Antonio Frangioni, Antonio Manca

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


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
Authors: Andrew Goldberg, Antonio Frangioni, Antonio Manca

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


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
Authors: Antonio Frangioni, Antonio Manca, Matteo Sammartino



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
Author: Antonio Frangioni



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
Author: Alessandro Bertolini, Antonio Frangioni