## MinCost MaxFlow code

Moderator: Board moderators

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

### MinCost MaxFlow code

hi, in the past days i have read somewhat about the mincost maxflow algorithm, and i have realized this seems to be an "obscure" topic, because although there is information about the algorithms, little is covered about an actual implementation in a language like c++, this has been what i have learned

- You can solve it, by finding a maxflow, and then runnning succesive Bellman Ford to reduce the cost, in this case what seems difficult to me is finding the actual negative cycle, and i don't know if this is a efficient way to solve the problem.

- In the site of Igor Naverniouk, (http://shygypsy.com/tools/mcmf3.cpp), there is indeed a code to solve this problem, but it uses some algorithm that i don't understand, and as i see it uses some kind of Dijkstra, but as far as i know Djikstra can't be used for finding shortest path with negative weights, so i'm every time more confused.

So i'm asking for help, if you know any good resource with a good implementation, or can explain how the code above works, it would be very helpful, thanks in advance

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
(1) Finding the negative cycle is a very short extension of Bellman-Ford. This isn't really efficient, though.

(2) I haven't seen Igor's code yet, but I'm suspecting he is using the Cheapest Augmenting Path algorithm. The basic idea is to weight each node with a "potential", and for each edge (u,v), calculate a reduced cost

c'(u,v) = c(u,v) + p(u) - p(v)

where c(u,v) is the original cost of the edge and p(u) and p(v) are the potentials of the node.

If there are no negative cycles in the graph, then if for each node, we use the shortest distance from the source as the potential p, then all reduced costs are non-negative by the triangle inequality. Then Dijkstra can be used to find an augmenting path of minimal reduced cost from source to sink (which is also the minimal un-reduced cost path).

Note that you don't need all edge weights to be non-negative, just have no negative weight cycles. You can use an initial Bellman-Ford to calculate the initial potentials this way.

With each augmenting path found, the potentials can be updated by

p'(u) = p(u) + d(s,u)

where d(s,u) is the shortest path distance to u from source s using the current reduced costs. It can be proven that all reduced costs remain non-negative. Then Dijkstra can be used again and again until no augmenting path can be found, in which case you have a max-cost min-flow.

Interestingly enough, this algorithm gives the minimum-cost flow for every possible (non-negative) flow value from source to sink.

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm
ok, thanks for replying, i think i have understood now, and i think i have implemented right, i just have some doubts, maybe you can answer me:

(1) why the potential assigned to each vertex grantes us that there is no negative path?

(2) i dont understand how can i modify this algorithm to allow negative costs, could you explain a little more

(3) what about the maxcost-maxflow problem, how can this algorithm be modified to give us the flow with maxcost?

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA
(1) Assuming no negative cycle, the following inequality ALWAYS holds:

d(s,v) <= d(s,u) + c(u,v) --- (1)

for all u,v where s is the starting vertex, d(s,u) and d(s,v) minimum distances to vertices u and v and c(u,v) the cost of the edge between u and v.

Rearranging gives c(u,v) + d(s,u) - d(s,v) >= 0 and therefore setting the initial potential of a vertex to be the minimum distance from s to it will always result in initial non-negative reduced costs.

To prove that the reduced costs always remain non-negative, use induction. I'll give a brief outline of the proof - the details can be found online:

After augmentation, we have p'(u) = p(u) + d'(s,u) where p is the original potential, p' the new potential, and d'(s,u) the distance from s to u under potential p (the original potential).

For any edge (u,v), the new reduced cost is now changed by d'(s,u) - d'(s,v). If an edge in the new residual network was previously in the old residual network, we can again appeal to the triangle inequality (1) above.

If an edge (u,v) in the new residual network was not in the old residual network, then (v,u) must be on some shortest path from s to t. Then the reduced cost on (u,v) must then be equal to 0, because d'(s,v) = d'(s,u) + c'(u,v) where c'(u,v) is the old reduced cost on (u,v) and the new reduced cost is c'(u,v) + d'(s,u) - d'(s,v) = 0.

(2) Again, if there are no negative cycles (but negative costs), we can assign initial potentials by shortest path distances from the source node. The shortest path distances can be found by Bellman-Ford.

(3) Negate all costs. Again, after negation we need to avoid negative-cost cycles.

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm
Thanks for your help, now i think i understand the problem well, and solved several problems too , thanks again

cpphamza
New poster
Posts: 18
Joined: Sat Sep 09, 2006 12:55 pm
I'm trying to solve this problem http://acmicpc-live-archive.uva.es/nuev ... php?p=3562 which is very much related to this thread but always get WA

actually i'm using Igor's code for mincost max flow, and for max cost I let cost[j] = MaxCost we got-cost[j] and rerun the mincost maxflow.

I tried to multiply each float number of the input by 100 and work with integers only and divide at the end but also got WA.

Can anyone give a hint to a special case or a probable mistake?
Thanks

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

### world finals,2006 Problem B

hello ,
igor once told me that his min cost max flow code given in his site doesnt work for the problem u mentioned . this is the problem of the world finals , 2006 problem B . so u may check with igor in this matter . may be he can help . or u can write a min cost max flow code on ur own .
happy coding
bye bye
In good company

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
The code works on that problem. Frank Chu (the co-author of the code) has just got it accepted. You must have a bug in the way you are using it.
If only I had as much free time as I did in college...

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm
thanx igor for ur concern . now iLL try to get the problem accepted . thanx for all the codes in ur site . it is a nice learning curve for newcomer like us .
bye bye
In good company

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
can anyone provide me with some links or soft book/tutorial/pdf for network flow algorithm and its variations??
Syed Ishtiaque Ahmed Kallol
CSE,BUET

rMegaS
New poster
Posts: 6
Joined: Mon Jul 30, 2007 5:51 am
Location: Russia
Contact:

### network flow pdf

Kallol wrote:can anyone provide me with some links or soft book/tutorial/pdf for network flow algorithm and its variations??
here's couple:
http://ww3.algorithmdesign.net/handouts/MaxFlow.pdf
http://web.mit.edu/15.053/www/AMP-Appendix-C.pdf
http://activities.tjhsst.edu/sct/lectures/netflow.pdf

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
Thnak you ...great help

Now can you give me similar links for hangariun methods for solving bipartite matching problem??
Syed Ishtiaque Ahmed Kallol
CSE,BUET

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
http://www.topcoder.com/tc?module=Stati ... d2=maxFlow

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
What is the best complexity for bipertite matching problem ?? I can code a dfs like code with complexity O(m*n*n). Is there any better algo??
Syed Ishtiaque Ahmed Kallol
CSE,BUET