Archiv für April, 2013

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.

5 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.

3 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.