September 24th, 2016

Solving the Shortest Path Problem (1) – Intro

Shortest Path Problem

3 years later I’m back with a new article in my blog – time flies..

The Shortest Path Problem is a common problem to nearly anyone nowadays. Anyone who used a navigation system or Google Maps for finding the best route for the weekend trip has already sucessfully solved the shortest path problem.
A solution to the shortest path (in terms of distance, time or any arbitiary cost) is to find the best route from one point of a network (maybe a street network) to another.

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

https://en.wikipedia.org/wiki/Shortest_path_problem

There are several tools for solving this problem – even free of charge and on any platform. In the following article series I want to explore the usage and the performance of various graph libraries that offer a shortest path solver.

The list of the packages:

  • igraph
  • Boost Graph Library (BGL)
  • LEMON Graph Library
Be the first to like.
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?

1 andere Person mag diesen Artikel.
April 10th, 2013

Solving the Minimum Cost Flow Problem (6) – Google or-tools

Push-relabel algorithm: Google or-tools

At last we will solve the instance of a Minimum cost flow problem described in (1) with Google or-tools. Node 1 is the source node, nodes 2 and 3 are the transshipment nodes and node 4 is the sink node.

mcf_dimacs_1

So let’s see how the python API of google or-tools work:

# import graph from google or-tools
from graph import pywrapgraph

# Create graph
# Attention: add +1 for number of nodes and arcs, if your node-IDs begin with 1
# because google or-tools mcf solver internal counters are strictly zero-based!
num_nodes = 4 + 1
num_arcs = 5 + 1
# args: NumNodes * NumArcs
G = pywrapgraph.StarGraph(num_nodes, num_arcs)

# create min cost flow solver 
min_cost_flow = pywrapgraph.MinCostFlow(G)

# add node to graph with positive supply for each supply node 
min_cost_flow.SetNodeSupply(1, 4)
# add node to graph with negative demand for each demand node 
min_cost_flow.SetNodeSupply(4, -4)
# you can ignore transshipment nodes with zero supply when you are working with
# the mcfp-solver of google or-tools

# add arcs to the graph
arc = G.AddArc(1, 2)
min_cost_flow.SetArcCapacity(arc, 4)
min_cost_flow.SetArcUnitCost(arc, 2)
arc = G.AddArc(1, 3)
min_cost_flow.SetArcCapacity(arc, 2)
min_cost_flow.SetArcUnitCost(arc, 2)
arc = G.AddArc(2, 3)
min_cost_flow.SetArcCapacity(arc, 2)
min_cost_flow.SetArcUnitCost(arc, 1)
arc = G.AddArc(2, 4)
min_cost_flow.SetArcCapacity(arc, 3)
min_cost_flow.SetArcUnitCost(arc, 3)
arc = G.AddArc(3, 4)
min_cost_flow.SetArcCapacity(arc, 5)
min_cost_flow.SetArcUnitCost(arc, 1)

# solve the min cost flow problem
# flowDict contains the optimized flow
# flowCost contains the total minimized optimum
min_cost_flow.Solve()
flowCost = min_cost_flow.GetOptimalCost()

print "Optimum: %s" %flowCost

As one can see the python API of google or-tools is also pretty handy although everything is coded in C++. The python API was created using SWIG. The biggest caveat one can run into is the fact that the MCFP solver in google or-tools is strictly zero based. So adding nodes starting from 1 ..n result in strange errors if you don’t size the initial graph properly: just add +1 to the number of nodes and the number of arcs if your node ids start with 1.

Alternatively you can pass the proper number of nodes and arcs at the graph initialization and substract -1 from all of your node ids so they are zero based. But be careful – any arc is made of the node ids so you’ll have to substract -1 at the arcs level also.

Be the first to like.
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.

4 Leute mögen diesen Artikel.
April 6th, 2013

Solving the Minimum Cost Flow problem (4) – PuLP

Linear program solvers: PuLP

We will solve the instance of a Minimum cost flow problem described in (1) now with another linear program solver: PuLP. Node 1 is the source node, nodes 2 and 3 are the transshipment nodes and node 4 is the sink node.

mcf_dimacs_1

While lpsolve has this nice feature of reading DIMACS network flow problems, PuLP has nothing comparable to offer. So we have to transform the whole network flow problem into a plain linear program on our own.

At the PuLP wiki I found a sample for solving the transshipment problem with PuLP. Actually these code snippets work also for the minimum cost flow problem but in the original code there is a typo:

Wrong:

for n in Nodes:
    prob += (supply[n]+ lpSum([route_vars[(i,j)] for (i,j) in Arcs if j == n]) >=
             demand[n]+ lpSum([route_vars[(i,j)] for (i,j) in Arcs if i == n])), \
            "Steel Flow Conservation in Node:%s"%n

Right:

for n in Nodes:
    prob += (supply[n]+ lpSum([route_vars[(i,j)] for (i,j) in Arcs if j == n]) >=
             demand[n]+ lpSum([route_vars[(i,j)] for (i,j) in Arcs if i == n])), \
            "Steel Flow Conservation in Node %s"%n

The problem in the original code is the colon (‘:’) at 'Steel Flow Conservation in Node:%s"%n'. This causes the generation of an incorrect *.lp file that is generated when you use PuLP. This *.lp file will be sent to a solver package of your (or PuLP’s) choice. So just remove the colon in this line.

Here we go with the full working code for our sample instance of the MCFP:

'''
Minimum Cost Flow Problem Solver with PuLP
Adapted from:

https://code.google.com/p/pulp-or/wiki/ATransshipmentProblem

The American Steel Problem for the PuLP Modeller
Authors: Antony Phillips, Dr Stuart Mitchell   2007

'''

# Import PuLP modeller functions
from pulp import *

# list of nodes
nodes = [1,2,3,4]

# supply or demand of nodes
            #NodeID : [Supply,Demand]
nodeData = {1:[4,0],
            2:[0,0],
            3:[0,0],
            4:[0,4]}

# arcs list
arcs = [ (1,2),
         (1,3),
         (2,3),
         (2,4),
         (3,4)]

# arcs cost, lower bound and capacity
            #Arc : [Cost,MinFlow,MaxFlow]
arcData = { (1,2):[2,0,4],
            (1,3):[2,0,2],
            (2,3):[1,0,2],
            (2,4):[3,0,3],
            (3,4):[1,0,5] }

# Splits the dictionaries to be more understandable
(supply, demand) = splitDict(nodeData)
(costs, mins, maxs) = splitDict(arcData)

# Creates the boundless Variables as Integers
vars = LpVariable.dicts("Route",arcs,None,None,LpInteger)

# Creates the upper and lower bounds on the variables
for a in arcs:
    vars[a].bounds(mins[a], maxs[a])

# Creates the 'prob' variable to contain the problem data    
prob = LpProblem("Minimum Cost Flow Problem Sample",LpMinimize)

# Creates the objective function
prob += lpSum([vars[a]* costs[a] for a in arcs]), "Total Cost of Transport"

# Creates all problem constraints - this ensures the amount going into each node is 
# at least equal to the amount leaving
for n in nodes:
    prob += (supply[n]+ lpSum([vars[(i,j)] for (i,j) in arcs if j == n]) >=
             demand[n]+ lpSum([vars[(i,j)] for (i,j) in arcs if i == n])), \
            "Flow Conservation in Node %s"%n

# The problem data is written to an .lp file
prob.writeLP("simple_MCFP.lp")

# The problem is solved using PuLP's choice of Solver
prob.solve()

# The optimised objective function value is printed to the screen    
print "Total Cost of Transportation = ", value(prob.objective)

The code is well commented. For a very detailed description have a look at the wiki of PuLP. Because there is no special network component in the PuLP modeler – any problem to solve is a linear program. So you have to write any instance of a MCFP as a plain LP which is not easy to understand at first glance.

2 Leute mögen diesen Artikel.
April 6th, 2013

Solving the Minimum Cost Flow problem (3) – lpsolve

Linear program solvers: Lpsolve

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

mcf_dimacs_1

As lpsolve can read the DIMACS file format we don’t have to transform a graph structure into a plain linear program. The XLI (eXtensible language interface) does this for us.
A good description of the DIMACS Minimum cost flow problem file format can be found here.
So for solving our MCFP we just have to write down the MCFP in DIMACS file format with a text editor of our choice (I called the file ‘simple_MCFP.net’) and let lpsolve do the dirty work:


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

Here is the python code for solving a minimum cost flow problem in DIMACS file format with the python API of lpsolve:

from lpsolve55 import *

# full file path to DIMACS file
path = 'simple_MCFP.net'

# read DIMACS file and create linear program
lp = lpsolve('read_XLI', 'xli_DIMACS', path)

# solve linear program
lpsolve('solve', lp)

# get total optimum
optimum = lpsolve('get_objective', lp)

print optimum #should be 14

When you are working with the python API of lpsolve you’ll always have to call the function lpsolve() and pass the C method you want to access as first argument as string, e.g. lpsolve(‘solve’, lp). So obviously this API is a very thin layer upon the C library underneath.

The usage of the python API of lpsolve is not really pythonic because lpsolve is written in C – but hey: it works!  The complete list of functions can be found here.

Be the first to like.
März 31st, 2013

Solving the Minimum Cost Flow Problem (2) – Software

I don’t want to give you a complete overview of MCFP solvers because I just dipped into the world of linear and network flow programming. Instead of this I just want to mention a few MCFP solvers that I have tested. Python will be the programming language for the test – so I checked solvers with the corresponding language bindings.

Linear program solvers

As mentioned in the previous article one can solve MCFP also as ordinary linear programs. So here are the two packages I tested.

 

lpsolve is a Mixed Integer Linear Programming (MILP) solver written in C released under the LGPL. You can use lpsolve on Windows and Linux systems. For windows there is a nice GUI which is called LPSolveIDE. It reads several LP file formats such as *.mpl, *.lp and also the DIMACS file format which is used for network flow problems. Furthermore it has a rich API: you can use lpsolve with .NET (there is even a lpsolve plugin for Microsofts Solver Foundation MSF!), Java, PHP and Python.

 

PuLP is kind of a python wrapper for various (LP) solver packages released under the MIT license:

 PuLP is an LP modeler written in python. PuLP can generate MPS or LP files and call GLPK (http://www.gnu.org/software/glpk/glpk.html), COIN (http://www.coin-or.org/), CPLEX (http://www.cplex.com/), and GUROBI (http://www.gurobi.com/) to solve linear problems.

 

Specialized MCFP solvers

As the MCFP is a special linear program that can be solved more efficiently with algorithms that exploit the network structure you should also have a look at specialized solvers around.

 

NetworkX is a pure Python library that deals with graphs:

NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks (http://networkx.github.com/).

The API is not very hard to learn, it’s well documented and obviously there is a active user community. NetworkX is released under the BSD license. It offers algorithms for many graph related issues (complete list here):

  • Clustering
  • Shortest Paths (Dijkstra, A*, Bellman-Ford, Floyd-Warshall)
  • Network flows (Minimum cost flow, maximum cost flow, minimum cut, Maximum flow minimum cost)
  • Minimum spanning tree

 

Google or-tools are a set of tools that deal not only with graph structures and algorithms but also with various other issues related to Operations Research (OR). This package is released under the Apache 2.0 license:

This project hosts operations research tools developed at Google and made available as open source. The project contains several tools:

  • A Constraint Programming solver.
  • A wrapper around third-party linear solvers (GLPK, CLP, CBC, SCIP, Sulum).
  • Knapsack algorithms.
  • Graph algorithms (shortest paths, min-cost flow, max flow, linear sum assignment).

Everything is coded in C++ and is available through SWIG in Python, Java, and .NET (using Mono on non-Windows platforms) (http://code.google.com/p/or-tools/).

Ok that’s it for now – let’s dive into the API of the packages in the next articles..

1 andere Person mag diesen Artikel.
März 24th, 2013

Solving the Minimum Cost Flow Problem (1) – Intro

Minimum cost flow problem: a short description

The Minimum cost flow problem (MCFP) is a generalized network flow problem that describes the goal of minimizing the total cost of flow through a network made of arcs and nodes which contains source, sink and transshipment nodes.

The minimum-cost flow problem is to find the cheapest possible way of sending a certain amount of flow through a flow network. Solving this problem is useful for real-life situations involving networks with costs associated (e.g. telecommunications networks), as well as in other situations where the analogy is not so obvious, such as where to locate warehouses (http://en.wikipedia.org/wiki/Minimum-cost_flow_problem).

Source nodes emit flow while sink nodes absorb flow. The flow through transshipment nodes is only intermediate: inflow must be equal to outflow at these nodes: so the net flow at these nodes is zero. Additionally there are maximum flow capacities on each arc of the network, i.e. it is not allowed that the amount of flow through a certain arc exceeds the maximum capacity specified on this arc.

In the following picture node 1 has 4 units of supply (= source node with positive value), node 4 has 4 units of demand (sink node with negative value) while nodes 2 and 3 are only transshipment nodes with a supply of zero. On the arcs you find lower flow bounds, upper flow bounds (or capacities) and costs. The goal is to ship 4 units from node 1 to node 4 with the lowest costs and without violation of the flow constraints (lower and upper bounds on the arcs).

Instance of a Minimum Cost Flow Problem

Instance of a Minimum Cost Flow Problem (http://lpsolve.sourceforge.net/5.5/DIMACS_mcf.htm)

The Minimum cost flow problem can be seen as a general problem from which various other network flow problems can be derived:

  • Transportation problem
  • Transshipment problem
  • Assignment problem
  • Shortest path (tree) problem

A special case of the Minimum Cost Flow Problem is the famous transportation problem (TP). In a regular TP the network lacks transshipment nodes and capacities on the arcs. So it’s a simpler version of the MCFP. The transshipment problem comes with transshipment nodes but lacks capacities on the arcs of the network. The assignment problem is a special version of the transportation problem and you can even solve a shortest path (tree) problem as a MCFP. Read more on the theoretical background here.

So in short: if you have a MCFP-Solver at hand you are able to solve various problems with this package.

The assignment problem is a special case of the transportation problem, which is a special case of the minimum cost flow problem, which in turn is a special case of a linear program. While it is possible to solve any of these problems using the simplex algorithm, each specialization has more efficient algorithms designed to take advantage of its special structure (http://en.wikipedia.org/wiki/Assignment_problem).

As stated in this quote and in previous articles, you can describe and solve a MCFP as a Linear program with an ordinary LP solver package. The simplex algorithm will likely be applied in this case. Or you can speed up things (magnitudes faster!) with a solver that is specialized on network flow problems and exploits the network structure of the MCFP: a network simplex solver or the push-relabel algorithm.

More on this in the next articles..

1 andere Person mag diesen Artikel.
März 6th, 2013

Linux 64Bit auf Samsung P560

Seit geraumer Zeit nutze ich Ubuntu und OpenSUSE 64Bit auf meinem Samsung Notebook P560. Die Installation funktionierte jedoch – egal welche Distribution – immer nur, wenn beim Starten des Kernels die Option ‘acpi=off’ gesetzt wurde.

Damit ließ sich Linux auch auf dem Notebook installieren. Allerdings störte mich folgendes immer mehr:

  • beim Anschluss des Stromkabels im laufenden Betrieb stürzte das System ab
  • auch beim Entfernen des Stromkabels gab es jedes Mal einen Reboot (beide Fälle wohlgemerkt mit vollem Akku..)
  • das Betätigen der Funktionstasten zur Helligkeitseinstellung des Bildschirms (Fn) führten zum Absturz
  • das Samsung Galaxy Tab wurde nicht per mtpfs erkannt
  • der SD-Slot wurde von Linux nicht erkannt

Nach einigem Suchen fand ich immer wieder den Hinweis auf ein möglicherweise veraltetes BIOS. Meine Version war 10LU. Samsung bietet für den P560 auch ein BIOS Update an: das 11LU. Leider gibt es die Software zum Flashen des BIOS nur für Windows.

Also Windows starten, das Update von Samsung runterladen, BIOS flashen mit der Software und neustarten. So einfach sollte es eigentlich sein. Leider stellte sich dann nach etlichen Versuchen, die alle mit der Medung “Fehler: Treiber konnte nicht geladen werden” abgebrochen haben heraus, dass man die Software unter Windows 7 mit dem Kompabilitätsmodus für Windows XP ausführen muss. Und siehe da: es funktionierte.

Seit ich das BIOS in der Version 11LU drauf habe, funktioniert auch Linux 64Bit mit ACPI wunderbar. Keine Abstürze mehr. Und es ist nun ein vollwertiges Notebook. Auch das Samsung Galaxy Tab wurde nun von den mtpfs-Tools erkannt.

Ab jetzt wird bei mir Windows  sein Dasein endgültig in einer virtuellen Gast-Maschine fristen..

3 Leute mögen diesen Artikel.
Oktober 24th, 2012

GRASS GIS v.out.ogr vs ogr2ogr

In der aktuellen stabilen Version von GRASS GIS 64bit (6.4.2) ist der Export von Geodaten per v.out.ogr extrem langsam. Zum Glück gibts dafür eine schnelle Lösung: die OGR Tools.

Mit der Installation von OGR wird auch das Werkzeug ogr2ogr mitgeliefert. Und das kann sehr schnell auch Daten im GRASS GIS Format lesen und ein anderes Geodatenformat schreiben. Leider ist der Zugriff mit diesem Werkzeug auf die GRASS GISBASE nicht sehr umfangreich dokumentiert.

Dabei gilt folgendes Format des Exportbefehls:

ogr2ogr <OUTPUTSHAPEFILENAME>.shp <$GISBASE/<LOCATION>/<MAPSET>/vector/<LAYERNAME>/head <LAYERNUMMER> [-nlt <OGRGEOMETRYTYPE>]

Hier ein Beispiel, wie ein GRASS Layer in ein ESRI Shapefile vom Typ Multipolygon geschrieben wird.

ogr2ogr /home/GISDATA/shp/lakes.shp /home/GISDATA/GRASS/Bayern/testdata/vector/lakes/head 1 -nlt MULTIPOLYGON

 

Be the first to like.