pyMCFsimplex – Efficient Solving of Minimum Cost Flow Problems in Python

pyMCFsimplex – a Python Wrapper for MCFSimplex

pyMCFimplex is a Python-Wrapper for the C++ MCFSimplex Solver Class from the Operations Research Group at the University of Pisa. MCFSimplex is a piece of software hat solves big sized Minimum Cost Flow Problems very fast through the (primal or dual) network simplex algorithm. Also important: MCFSimplex is open source software – it has been released under the LGPL license.

To get a feeling for the performance of MCFSimplex: it solves a MCFP of 50.000 nodes and 500.000 arcs in 5 seconds on a average linux box (2,2Ghz 6GB RAM, Ubuntu 64Bit). Another one: NetworkX (a pure python graph library) also has an implementation of the network simplex algorithm – but this one is magnitudes slower than e.g. MCFSimplex. I tried so solve the same MCFP (n = 50.000, m = 500.000) with NetworkX and terminated the process after 1 hour. I intend to publish more on performance tests in an upcoming article.
See also this paper for a MCFP benchmarks.

You may ask: So what about pyMCFsimplex? Well, you’ll get the performance of a well coded C++ MCFP solver with the simplicity of a Python API. Isn’t this nice?

pyMCFsimplex was being made available using SWIG. Don’t ask for the time I spent on figuring out how SWIG works. With more knowledge in C++ I would have been faster – but I’m not a C++ guy! I want it in Python!

The authors of MCFSimplex are Alessandro Bertolini and Antonio Frangioni from the Operations Research Group at the Dipartimento di Informatica of the University of Pisa. Please visit their website for further information:

http://www.di.unipi.it/optimize/Software/MCF.html#MCFSimplex

Documentation

Please read the README first. Thank you.

Installation

Installation prerequisites are:

• Python 2.7 or Python 2.6 (only Windows)
• numpy (tested with 1.6.1)
• a build environment for source distribution install

Windows

Download the appropriate MSI package for your installed Python version (2.6 or 2.7) and simply execute the installer:

Linux

Download the binary dist package pyMCFSimplex-0.9.linux-x86_64.tar.gz

and untar it with the following

tar xfvz pyMCFSimplex-0.9.linux-x86_64.tar.gz

It will install into /usr/local/lib/python2.7/dist-packages/.

 

• for windows: start a command line as Administrator and run

python setup.py install

 

• for linux: start a terminal and run

sudo python setup.py install

Usage

Hey! Wait a minute! Please note that pyMCFSimplex’s version is 0.9. So this is not productive! I tested all the relevant methods and all of my tests went fine, but if you run into an error that occurs in the underlying C++ library Python might crash, because at the moment I don’t know yet how to deal with C++ exceptions and SWIG. Feel free to contact me, if you know more on this!

Now let’s see how the python API of pyMCFSimplex works:

from pyMCFSimplex import *
print "pyMCFSimplex Version '%s' successfully imported." % version()
mcf = MCFSimplex()
print "MCFSimplex Class successfully instantiated."
FILENAME = 'sample.dmx'
print "Loading network from DIMACS file %s.." % FILENAME
f = open(FILENAME,'r')
inputStr = f.read()
f.close()
mcf.LoadDMX(inputStr)

print "Setting time.."
mcf.SetMCFTime()
print "Solving problem.."
mcf.SolveMCF()
if mcf.MCFGetStatus() == 0:
    print "Optimal solution: %s" %mcf.MCFGetFO()
    print "Time elapsed: %s sec " %(mcf.TimeMCF())
else:
    print "Problem unfeasible!"
    print "Time elapsed: %s sec " %(mcf.TimeMCF())

As you can see the API is not too hard to understand, if you are familiar with optimization stuff. With these few lines of code above you’ve already got a DIMACS Minimum Cost Flow Problem solver at hand written in Python! You don’t even have to worry about parsing the DIMACS file format as you’ve got LoadDMX() out of the box. How cool is that?

The python API was created using SWIG, so you directly call C++ methods with a call like mcf.SolveMCF(). Thus you have to pass C datatypes if you want to pass someting – but don’t worry: there are helpers in pyMCFSimplex for that.

You’ll find more information in the README-file.

The sample script shows you all the important methods.