Artikel getaggt mit ‘Network simplex’

September 24th, 2013

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?

weiterlesen »

2 Leute mögen diesen Artikel.

April 10th, 2013

Solving the Minimum Cost Flow problem (5) – NetworkX

Network Simplex Solver: NetworkX

We will solve the instance of a Minimum cost flow problem described in (1) with NetworkX. Node 1 is the source node, nodes 2 and 3 are the transshipment nodes and node 4 is the sink node.

mcf_dimacs_1

Solving a Minimum Cost Flow Problem with NetworkX is pretty straight forward.

# import networkx
import networkx as nx

# create directed graph
G = nx.DiGraph()

# add node to graph with negative (!) supply for each supply node 
G.add_node(1, demand = -4)

# you can ignore transshipment nodes with zero supply when you are working with the mcfp-solver 
# of networkx
# add node to graph with positive (!) demand for each demand node
G.add_node(4, demand = 4)

# add arcs to the graph: fromNode,toNode,capacity,cost (=weight)
G.add_edge(1, 2, capacity = 4, weight = 2)
G.add_edge(1, 3, capacity = 2, weight = 2)
G.add_edge(2, 3, capacity = 2, weight = 1)
G.add_edge(2, 4, capacity = 3, weight = 3)
G.add_edge(3, 4, capacity = 5, weight = 1)

# solve the min cost flow problem
# flowDict contains the optimized flow
# flowCost contains the total minimized optimum
flowCost, flowDict = nx.network_simplex(G)

print "Optimum: %s" %flowCost  #should be 14

As you can see the code is very readable and easy to understand. The only thing you could get trouble with in the formulation of a min cost flow problem with networkx is the fact that the supply nodes get a negative supply value (because the python attribute is called „demand“) while the demand nodes require positive demand values.
This differs from the usual mathematical notation of supply and demand values in the network flow problems where supply values are positive and demand values of negative sign.
Also note that you only need to add supply and demand nodes to the graph. You don’t have to care of the transshipment nodes.

5 Leute mögen diesen Artikel.