Notebook 3.4 - Minimum Cost Flow (Transhipment) using PuLP¶
Let us now attempt to model the Transhipment or Minimum Cost Flow Problem, that we also covered in our session videos.
Setting up¶
from pulp import *
prob = LpProblem('prob', LpMinimize)
Entry of problem instance data¶
On our previous notebook, we created our objects one by one, through the declation of two arrays that contained all the objects that we needed to create.
S = ['S1', 'S2', 'S3']
D = ['D1', 'D2', 'D3']For this particular model however, we are going to try something else:
N = [str(i+1) for i in range(8)]
N
The above declaration created 8 node elements in our array, which were generated using an in-line for loop. For every value in a range of integers between 0 and 8, the str(i+1) command was adding a stringified version of the value, incremented by one.
The increment is essential if we want the list of node names to start from 1, since the range(8) command would return a series of 8 values, starting from 0. You can check this on your own below:
list(range(8))
Our list of supply/demand values is provided in a more "traditional" way. We use positive values to indicate that a node is a node supplier, null values to indicate transhipment nodes, and negative values to indicate demand nodes.
The values will be provided in the same sequence as the node IDs.
supply = [300, 300, 100, 0, 0, -200, -200, -300]
We can now convert this into a dictionary of values, with node IDs used as keys.
D = dict(zip(N, supply))
D
The nested dictionary of link costs is defined in a similar way as the one we discussed in our previous notebook.
C = {'1': {'4': 2, '5': 1},
'2': {'4': 1, '5': 2},
'3': {'4': 1, '5': 2},
'4': {'6': 1, '7': 2, '8': 1},
'5': {'6': 2, '7': 1, '8': 2}}
Our set of links is also created using using inline loop.
E = [(i,j) for i in N for j in N if i in C.keys() if j in C[i].keys()]
E
I appreciate that inline loops are a bit confusing at first. Let's try to recreate this result using a traditional loop.
E1 = []
for i in N: # for every node i in set N
for j in N: # for every node j in set N
if i in C.keys(): # if we have an inner dictionary in C for the costs of links beginning in i
if j in C[i].keys(): # and if that inner dictionary contains an entry for the node pair i,j
E1.append((i,j)) # then a link between i and j exists, and we will an entry to our set of links.
E1
And finally, we can declare our decision variables
x = LpVariable.dicts('x', E, lowBound = 0)
Objective and constraints¶
We will ne using the same objective function as before:
prob += lpSum([C[i][j] * x[i,j] for (i,j) in E])
Even though our flow conservation constraint might look a little bit intimidating on paper, I believe that it looks a lot more straightforward when transliterated into a PuLP command!
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]
Obtaining a solution¶
status = prob.solve()
print('SOLUTION:')
for v in prob.variables():
print(f'\t\t{v.name} = {v.varValue}')
print('\n') # Prints a blank line
print(f'OBJECTIVE VALUE: {prob.objective.value()}')
Summary¶
from pulp import *
prob = LpProblem('prob', LpMinimize)
# INSTANCE DEFINITION
supply = [300, 300, 100, 0, 0, -200, -200, -300]
N = [str(i+1) for i in range(8)]
D = dict(zip(N, supply))
C = {'1': {'4': 2, '5': 1},
'2': {'4': 1, '5': 2},
'3': {'4': 1, '5': 2},
'4': {'6': 1, '7': 2, '8': 1},
'5': {'6': 2, '7': 1, '8': 2}}
E = [(i,j) for i in N for j in N if i in C.keys() if j in C[i].keys()]
# DECISION VARIABLE GENERATION
x = LpVariable.dicts('x', E, lowBound = 0)
# PROBLEM FORMULATION
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]
# SOLUTION
status = prob.solve()
print(f'STATUS\n{LpStatus[status]}\n')
print('SOLUTION:')
for v in prob.variables():
print(f'\t\t{v.name} = {v.varValue}')
print('\n') # Prints a blank line
print(f'OBJECTIVE VALUE: {prob.objective.value()}')