**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.,

- exactly one source node;
- the capacities of all the arcs larger than or equal to the flow surplus of the (unique) source.

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:

- can also solve (although not very effectively) Quadratic separable MCFs;
- it is entirely open-source under the flexible LGPL license, and therefore can be used with little restriction in all environments.

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

License: LGPL

Author: Alessandro Bertolini, Antonio Frangioni