Mincost Maxflow - help!

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Mincost Maxflow - help!

Post by danielrocha » Sat Oct 01, 2005 12:37 pm

Hello everyone,

For the past few weeks I've been trying to code an algorithm for the Mincost Maxflow problem, but I've had a lot of problems. I see this problem as been very interesting, as there are a lot of problems that can be solved by it (10594, 2691, 10888, 10746 come to mind). I was hoping you could help me. Here's the deal:

1. I've coded the Min Mean Cycle Canceling algorithm, only later to realize his time complexity is O(n^2*m^3*log n) which is, obviously, pretty huge. My algorithm seems to be ok, but I can't get past TLE in any of those problems I mentioned earlier.

2. I'm not sure even which algorithm I should code. I've encountered references to some algorithms: Min Mean Cycle Canceling, Cost Scaling and Sucessive Shortest Paths. The best among these seems to be the "Cost Scaling", which I think has complexity O(n^2*m*log (nC)) - where C is an upper bound on the edges cost.

I have two problems: first of all, I can't find any good material on these algorithms. Googling only got me some .ppts and very general description of them. Does anybody have a good text on any of these? My second issue is that even the "best" one of the mentioned algorithms has a "big" time complexity: for instance on problem 10594 n=100 and m=5000, so we have O(100*100*5000*log (100*C)), and that is a very big time complexity.

If someone could help, comment or point me in the right direction I would really appreciate.
Daniel
UFRN HDD-1
Brasil

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Re: Mincost Maxflow - help!

Post by nnahas » Sat Oct 01, 2005 10:05 pm

Cost scaling(which is a cost scaling variant of successive shortest paths). has O(nm lg U) complexity.
[Edit]: sorry what I said above is totally wrong

In fact, one of the fastest algo is the double scaling algorithm which has a time complexity of O(nm logU log (nC) (Ahuja, Magnanti &Orlin, Network Flows). (U is max capacity, C is max cost)

Also for some applications successive shortest paths can yield O(m lg N) , for example in prob 10806 .

See these links:
http://ocw.mit.edu/NR/rdonlyres/Electri ... ribe13.pdf

http://ocw.mit.edu/NR/rdonlyres/Electri ... ribe14.pdf

http://www.core.org.cn/NR/rdonlyres/Slo ... stpath.pdf
[EDIT2] double scaling, which is asymptotically one of the fastest is described here:
ftp://reports.stanford.edu/pub/cstr/rep ... 8-1227.pdf

But I don't think it is necessary for contest. usually successive shortest path is enough
Last edited by nnahas on Sat Oct 01, 2005 11:36 pm, edited 2 times in total.

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Thank you!

Post by danielrocha » Sat Oct 01, 2005 10:14 pm

Thank you so much for the links nnahas. They seem to be exactly what I've been looking for. I'm gonna read them and if I have any other problems I'll post here.

Thanks again
Daniel
UFRN HDD-1
Brasil

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

well

Post by wook » Sun Oct 02, 2005 2:35 pm

well,

there are many algorithms for mincost-maxflow problem, the fast and efficient, and the slow,
I only use one, which uses successive shortest path method,
and its time complexity is about o(|f|n^2)
I use this because it is just easy to write!

I think it is quite slow;
but in 10594 problem, it gives me quite satisfactory result.

also, by using this algorithm, minimum/maximum bipartite matching is about O(n^3), (precisely n * m * min(n, m) ), where n and m is the size of set, respecitvely.


it's sure that more efficient algorithms work better;
but they are difficult to understand and to write.


they are enough for many problems in programming contest, aren't they?
i hope that it could be a helpful advice. :lol:
Sorry For My Poor English.. :)

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Still...

Post by danielrocha » Tue Oct 04, 2005 4:24 pm

I've read about 200 times each of these .pdfs, but I can't quite understand the algorithm :oops: My code is something like this:

Code: Select all

1. Run a Dijkstra and set the initial "potencial" value on the nodes to -d[i], where d[i] is the minimum distance from the source node to the node i.
2. Run a BFS and augment the path (augment with the minimum edge capacity of the path) with cost 0 from the source to the destination.
3. If there isn't a path from the source to the destination in the new residual graph, break.
4. Run a Dijkstra and set the node "potencial" values to pot[i] = pot[i]-d[i] where pot[i] is the potencial and d[i] is the shortest distance from the source to node i. Goto 2.
Is this correct? I'm getting WA on the problem 10594. :(

I've a lot of questions about whats described on the texts, for instance: can I augment the shortest path with the minimum capacity edge of the path or should I augment it 1 by 1 unit of flow?

I'm very sorry for my english, if someone doesn't quite get what I'm trying to say, please tell me so I can try to make myself clear.

Thanks again, :D
Daniel
UFRN HDD-1
Brasil

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Re: Still...

Post by nnahas » Tue Oct 04, 2005 8:18 pm

danielrocha wrote:I've read about 200 times each of these .pdfs, but I can't quite understand the algorithm :oops: My code is something like this:

Code: Select all

1. Run a Dijkstra and set the initial "potencial" value on the nodes to -d[i], where d[i] is the minimum distance from the source node to the node i.
2. Run a BFS and augment the path (augment with the minimum edge capacity of the path) with cost 0 from the source to the destination.
3. If there isn't a path from the source to the destination in the new residual graph, break.
4. Run a Dijkstra and set the node "potencial" values to pot[i] = pot[i]-d[i] where pot[i] is the potencial and d[i] is the shortest distance from the source to node i. Goto 2.
Is this correct? I'm getting WA on the problem 10594. :(

I've a lot of questions about whats described on the texts, for instance: can I augment the shortest path with the minimum capacity edge of the path or should I augment it 1 by 1 unit of flow?

I'm very sorry for my english, if someone doesn't quite get what I'm trying to say, please tell me so I can try to make myself clear.

Thanks again, :D
No, it isn't exactly like that . The algorithm looks more like that:

Initialize all node potential nodes to 0;
residualnetwork = originalnetwork
while (flow out of source is not enough)
--Run Dijkstra on the residualnetwork and obtain the shortest path P
--Update node potentials by setting pot=pot-d
--Update edge costs by setting c(i,j) = c(i,j) - pot +pot[j]
--Push flow along P (you can push flow equal to the min capacity of the edges along P)
--Update the residual network according the flow you pushed
end while

Note: Of course when an edge gets deleted from the residual network you don't consider
it when doing Dijkstra anymore, until it gets reinserted.

I wrote a java 1.5 implementation of the algorithm in my academic work, I can email it to you if you PM me your email address.

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Thu Oct 06, 2005 9:00 pm

nnahas, I would like to thank you again for your help. As you can see here http://acm.uva.es/cgi-bin/OnlineJudge?P ... t:10594:50 we've been able to correct code the algorithm. As for anyone who's having difficulties with this algorithm, I have one suggestion: follow the pseudo-code in the above post :) The code for this algorithm end up being much smaller than the Hungarian Algorithm that we used for Mincost Bipartite Matching :D

There is one thing I would like to correct: when you say
--Update edge costs by setting c(i,j) = c(i,j) - pot +pot[j]

I believe it gives the impression that you should accumulate in the edge cost c(i,j) the values of - pot +pot[j], when what you really should do is something like c(i,j) = originalCost(i,j) - pot + pot[j]. I hope my explanation is clear enough.

There's one thing I would like to understand: if there are any negative cost edges in the graph, can I add the value of the most negative one to all of them (turning them positive) and use the SSP algorithm?

Thanks again everybody, :D
Daniel
UFRN HDD-1
Brasil

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas » Thu Oct 06, 2005 11:14 pm

danielrocha wrote: I believe it gives the impression that you should accumulate in the edge cost c(i,j) the values of - pot +pot[j], when what you really should do is something like c(i,j) = originalCost(i,j) - pot + pot[j]. I hope my explanation is clear enough.


Yes, you're right.

danielrocha wrote:
There's one thing I would like to understand: if there are any negative cost edges in the graph, can I add the value of the most negative one to all of them (turning them positive) and use the SSP algorithm?


No you can't do that, because adding the same (positive) number to all edges would favor paths which contain a small number of edges over the paths which contain a a large number of edges. e.g a 4 edge paths will see its cost increased by an amount that is twice as large as a 2 edge path, so that will result in a wrong answer.

But there's another way you can transform a network with negative edges to obtain an equivalent network without negative edges. You just push flow along the negative cost edge so as to saturate its capacity, which increases deficit by that amount of flow at the origin of the edge, and increases excess at the destination also by that same amount of flow. In the residual network this negative cost edge will be eliminated.

Post Reply

Return to “Algorithms”