# Setting up
!pip install pulp --progress-bar off
from pulp import *
prob = LpProblem('prob', LpMinimize)
Requirement already satisfied: pulp in /Users/pan/anaconda3/lib/python3.7/site-packages (2.0) Requirement already satisfied: pyparsing>=2.0.1 in /Users/pan/anaconda3/lib/python3.7/site-packages (from pulp) (2.4.7)
# Defining problem instance
N = ['A', 'B', 'C', 'D', 'E', 'F']
C = {'A': {'B': 5, 'C': 2},
'B': {'C': 1, 'D': 4, 'E': 3},
'C': {'D': 8},
'D': {'E': 2, 'F': 2},
'E': {'F': 4}}
D = {node: 1 if node is 'A' else -1 if node is 'F' else 0 for node in N}
# Preparing "tables"
E = [(i,j) for i in N for j in N if i in C.keys() if j in C[i].keys()]
# Declaring decision variables.
x = LpVariable.dicts('x', E, lowBound = 0, upBound = 1, cat = LpInteger)
PuLP does not have a built-in type for Boolean decision variables. To overcome this limitation we will be declaring our variables as integers (using LpInteger
), while constraining them to take values between 0 and 1.
# Declaring objectives
prob += lpSum([C[i][j]*x[i,j] for (i,j) in E])
for i in N:
prob += (lpSum([x[i,j] for j in N if (i,j) in E])
- lpSum([x[k,i] for k in N if (k,i) in E])) == D[i]
# Solving problem
status = prob.solve()
print(f'STATUS\n{LpStatus[status]}\n')
print('SOLUTION')
for v in prob.variables():
print(v.name, '=', v.varValue)
STATUS Optimal SOLUTION x_('A',_'B') = 1.0 x_('A',_'C') = 0.0 x_('B',_'C') = 0.0 x_('B',_'D') = 1.0 x_('B',_'E') = 0.0 x_('C',_'D') = 0.0 x_('D',_'E') = 0.0 x_('D',_'F') = 1.0 x_('E',_'F') = 0.0
import networkx as nx
from matplotlib import pyplot, collections
position = {'A': [0,0.5], 'B': [3,1], 'C': [3,0],'D': [7,0], 'E': [9, 1], 'F': [11,0]}
flow = [v.varValue*3 for v in prob.variables()]
G = nx.Graph()
G.add_nodes_from(N)
G.add_edges_from(E)
fig, ax = pyplot.subplots()
nx.draw(G, pos=position, with_labels=True)
lines = []
for (i,j) in E:
lines.append([(position[i][0], position[i][1]),(position[j][0], position[j][1])])
lc = collections.LineCollection(lines, linewidth=flow, colors='r')
ax.add_collection(lc)
<matplotlib.collections.LineCollection at 0x7f9e79c983d0>