Skip to main content

pyMCFSimplex is a Python Wrapper for MCFSimplex

Project description


  •   	          pyMCFSimplex                                *
    

  • Version 0.9.1 *

  • Johannes Sommer, 2013*

  1. What?

pyMCFSimplex is a Python-Wrapper for the C/C++ MCFSimplex Solver Class from the University of Pisa. MCFSimplex is a Class that solves big sized Minimum Cost Flow Problems very fast. See also [1] for a comparison.

  1. How?

pyMCFSimplex was being made through 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!

  1. Who?

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 [2].

pyMCFSimplex is brought to you by Johannes from the G#.Blog

http://www.sommer-forst.de/blog. 

Feel free to contact me: info(at)sommer-forst.de

  1. Installation

Installation prerequisites are:

  • Python 2.7 or Python 2.6 (only Windows)
  • numpy (tested with 1.6.1)
  • a build environment if you want to install from source distribution

4.1 Windows

Select the appropriate MSI package for your installed Python version (2.6 or 2.7) an simply execute the installer.

4.2 Linux

Untar the binary dist package pyMCFSimplex-0.9.1.linux-x86_64.tar.gz with

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

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

4.3 Source Distribution

Grab the pyMCFSimplex-0.9.1_src_dist.zip file, extract it and run

a) linux: sudo python setup.py install

b) windows: start a command line as Administrator and run

python setup.py install

  1. Usage

Here is a first start. "sample.dmx" must be in the same location of your python script. With these lines of code you can parse a minimum cost flow problem in DIMACS file format and solve it.

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())

If you want to load a network not from a DIMACS file, you'll have to call LoadNet() while passing C-arrays to the method. C arrays in Python? Yes - don't worry. There are helper methods in pyMCFSimplex, that'll do this for you. Look at the following piece of code.

mcf = MCFSimplex() print "MCFSimplex Class successfully instantiated." print "Reading sample data.."

''' Problem data of a MCFP in DIMACS notation

c Problem line (nodes, links) p min 4 5 c c Node descriptor lines (supply+ or demand-) n 1 4 n 4 -4 c c Arc descriptor lines (from, to, minflow, maxflow, cost) a 1 2 0 4 2 a 1 3 0 2 2 a 2 3 0 2 1 a 2 4 0 3 3 a 3 4 0 5 1 '''

MCFP problem transformed to integers and lists

nmx = 4 # max number of nodes mmx = 5 # max number of arcs pn = 4 # current number of nodes pm = 5 # current number of arcs pU = [4,2,2,3,5] # column maxflow pC = [2,2,1,3,1] # column cost pDfct = [-4,0,0,4] # node deficit (supply/demand) pSn = [1,1,2,2,3] # column from pEn = [2,3,3,4,4] # column to

call LoadNet() with the return values of the helper methods

e.g. CreateDoubleArrayFromList(pU) takes a python list and returns a pointer to a

corresponding C array, that is passed as an argument to the method LoadNet()

mcf.LoadNet(nmx, mmx, pn, pm, CreateDoubleArrayFromList(pU), CreateDoubleArrayFromList(pC), CreateDoubleArrayFromList(pDfct), CreateUIntArrayFromList(pSn), CreateUIntArrayFromList(pEn))

print "Setting time.." mcf.SetMCFTime() 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())

Please check out the sample script gsharpblog_mcfsolve_test.py for more information.

  1. Good to know

I changed the original source code of MCFClass.h a little bit for SWIG compatibility. All changes are marked by the following comment line "//Johannes Sommer". This included:

  • LoadDMX() accepts in pyMCFSimplex a string value (original: c iostream). The original LoadDMX method is omitted.
  • as SWIG cannot deal with nested classes, I pulled the classes Inf, MCFState and MCFException out of the main class MCFClass.

Perhaps the above mentioned changes to the original source is not necessary, if you know SWIG very well. But I could not figure out how to get these things to work in the SWIG interface file. Useful hints are very welcome.

[1] http://bolyai.cs.elte.hu/egres/tr/egres-13-04.ps [2] http://www.di.unipi.it/optimize/Software/MCF.html#MCFSimplex

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

pyMCFSimplex-0.9.4.tar.gz (164.9 kB view details)

Uploaded Source

Built Distribution

pyMCFSimplex-0.9.4-cp39-cp39-macosx_10_15_x86_64.whl (278.9 kB view details)

Uploaded CPython 3.9macOS 10.15+ x86-64

File details

Details for the file pyMCFSimplex-0.9.4.tar.gz.

File metadata

  • Download URL: pyMCFSimplex-0.9.4.tar.gz
  • Upload date:
  • Size: 164.9 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/4.0.1 CPython/3.9.10

File hashes

Hashes for pyMCFSimplex-0.9.4.tar.gz
Algorithm Hash digest
SHA256 b00be330d9e3d49e389a92ebeeb5590293834fec51ba2df9096e805985bff00f
MD5 484fb809adc10ee68b55c407aa615e20
BLAKE2b-256 c369fb575c467ba91ccd12e7280e55cb432daf659ce2a09a29a7480357b94b1c

See more details on using hashes here.

File details

Details for the file pyMCFSimplex-0.9.4-cp39-cp39-macosx_10_15_x86_64.whl.

File metadata

File hashes

Hashes for pyMCFSimplex-0.9.4-cp39-cp39-macosx_10_15_x86_64.whl
Algorithm Hash digest
SHA256 1b0c6d9677fbc8ed98490b5cc316fcce4192246379e65a0f58e3d2b3f4b2f061
MD5 108fea33efb77fcb1a5ddc6056db7478
BLAKE2b-256 79b41e04f2c7dd0cef31f12186c45dc71789d336ee15299ae6263db5420a3ddf

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page