[ ]

Minimum Cost Maximum Flow: Cycle Cancelling Algorithm

Minimum Cost flow problem is a way of minimizing the cost required to deliver maximum amount of flow possible in the network. It can be said as an extension of maximum flow problem with an added constraint on cost (per unit flow) of flow for each edge.

Algorithm (Pseudocode)

def CostNetwork(Graph G, Graph Gf):
Gc <- empty graph
for i in edges E:
if E(u,v) in G:
cf(u,v) = c(u,v)
else if E(u,v) in Gf:
cf(u,v) = -c(u,v)

def MinCost(Graph G):
Find a feasible maximum flow of G and construct residual graph Gf
Gc = CostNetwork(G, Gf)
while(negativeCycle(Gc)):
Increase the flow along each edge in cycle C by minimum capacity in the cycle C
Update residual graph(Gf)
Gc = CostNetwork(G,Gf)
mincost = sum of Cij*Fij for each of the flow in the graph
return mincost

Note 1: To find a feasible maximum flow of $G$, use Ford Fulkerson’s Algorithm.

def FordFulkerson(Graph G, Node S, Node T):
Initialise flow in all edges to 0
while (there exists an augmenting path(P) between S and T in residual network graph):
Augment flow between S to T along the path P
Update residual network graph
return

Note 2: To find a negative cycle in graph $G_c$, use Bellman Ford’s Algorithm

For a more detailed lecture, please refer to http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/mincost.4up.pdf.