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

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.