JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
What is the meaning of potential? | Reply
Honestly, the MCMF tutorial #1 is too scientific to me and it's quite hard for me to understand.

Maybe it's implicitly explained in the article, but I don't get:
- what is the meaning of "potential" and "reduced cost"?
- what do we achieve by having "reduced cost"? (why do we need them?)
Re: What is the meaning of potential? (response to post by felix_halim) | Reply
I have implemented this algorithm and now I have my template of it. I'll think for a while to remember how does it work. I can answer your second question. By using potentials and reduced costs you keep all required properties, you need to perform Dijkstra's algorithm to find an augmenting path.
Re: What is the meaning of potential? (response to post by felix_halim) | Reply
The potential of a node k is the length of the shortest path in the graph from the source to k. Then, to reduce the costs of the graph you calculate the transformed cost of each link (u,v) adding potential[v] - potential[u].

This is made to have a graph with no negative costs, so we could find the shortest path using Disjktra instead of BellmannFord, something like:

void MinCostMaxFlow(graph, src, sink) {
  // init cost with +inf, potential with 0 and tree with NULL
  vector<int> cost, potential; vector<edge_t*> tree;
  BellmannFord(graph, cost, tree, src);
  UpdatePotentials(cost, potential);
  for (path_t path; GetPath(tree, sink);) {
    Augment(path);
    Disjktra(graph, cost, tree, src, potential);
    UpdatePotentials(cost, potential);
  }
}


To update the potentials we just have to substract cost from the potential.
Re: What is the meaning of potential? (response to post by felix_halim) | Reply
I don't think the bit about potential is very well presented, so let me try to present it in words instead. Flow potentials are a way of transforming the network in a way that doesn't affect the optimal flow solution. We can then solve for the optimal solution in our new network and it will be the same as the optimal solution in the original network. The advantage of doing this is that it allows us to maintain positive edge weights, so we can use more efficient algorithms in the new network, such as Dijkstra rather than Bellman-Ford in the successive shortest path method.

The transformation trick is this: For each node i, assign a number πi (this can be anything you want) and add this value to the cost of any edge that originates at node i and subtract it from any edge that ends at node i. Now consider a flow in this new network. Any flow that is transient at node i, will come in on an edge where the cost has been reduced by πi and leave on an edge where it has been increased by πi, so the cost of this flow will be the same as if you hadn't applied the potential at all. The only place that the transformation affects the cost is where the flow isn't transient at the sources and sinks, but this flow is fixed (we know how much flow is entering and leaving at the sources and sinks by the way we set up the problem). Therefore the change in cost for this particular flow caused by the transformation to our new network is independent of how the flow travels through the network. Hence an optimal solution in the original network corresponds to an optimal solution in the new one too.

The next part of the trick comes in the successive shortest paths algorithm. If we set the flow potential of each node to be equal to the cost of the shortest path from our super-source to that node, and maintain this property after each augmentation, then we end up with all the edge-weights in our graph being positive, so we can use Dijkstra's algorithm to calculate the shortest augmenting paths.
Re: What is the meaning of potential? (response to post by jbernadas) | Reply
Does this mean if I use Bellman-Ford for the whole thing then I don't need to care about potentials? Like:

void MinCostMaxFlow(graph, src, sink) {
  BellmannFord(graph, cost, tree, src);
  for (path_t path; GetPath(tree, sink);) {
    Augment(path);
    BellmannFord(graph, cost, tree, src);
  }
}
Re: What is the meaning of potential? (response to post by StevieT) | Reply

The advantage of doing this is that it allows us to maintain positive edge weights, so we can use more efficient algorithms in the new network, such as Dijkstra rather than Bellman-Ford in the successive shortest path method.


Does this meas if the graph doesn't have negative weight then we don't need to care about potentials? In this case, without worrying the potentials, will Dijkstra alone still works?
Re: What is the meaning of potential? (response to post by felix_halim) | Reply
Does this mean if I use Bellman-Ford for the whole thing then I don't need to care about potentials?

Yes, you can do either negative-cycle detection or shortest augmenting path using Bellman-Ford without using potentials at all.

Does this meas if the graph doesn't have negative weight then we don't need to care about potentials?

Unfortunately no. An augmenting path can travel the wrong direction down a directed edge with positive cost if there is already flow on that edge. In this case the cost is taken to be the negative of the cost if you were going the right direction. So even if you only have positive costs in your graph you still might have to consider negative costs in your shortest augmenting path code.
Re: What is the meaning of potential? (response to post by felix_halim) | Reply
I've tested (using UVA 10594) that using Bellman-Ford alone can work without worrying about potentials. The reason why using Dijkstra alone will fail is that: in the middle of MCMF algorithm, it is possible to have negative edge weight for the reverse flow. Thus, the "potentials" is invented so that this negative edge weight doesn't appear in the middle of MCMF and will make it run correctly. Is that correct?

The code that uses Bellman-Ford alone to solve 10594 is in the edit. The code that uses Dijkstra + Potentials is in Abednego's library.

Thanks all, now I know when do I need the "potentials" :)
Re: What is the meaning of potential? (response to post by jbernadas) | Reply
I think it is safe to use Dijkstra for the first time since the graph won't have reverse flow initially, otherwise Abednego's library would be wrong :).
Re: What is the meaning of potential? (response to post by felix_halim) | Reply
Thanks. I haven't notice that.
Re: What is the meaning of potential? (response to post by StevieT) | Reply
I would like to clarify something to myself:
In the method Reduce cost c_rev should be set to 0. If at input I have edge (i,j) and (j,i), for some i and j, should I made 4 edges in that case (as I understood from tutorial) or I can avoid that making (j,i) as c_rev(i,j) and (i,j) as c_rev(j,i)? I have looked at written solution and felix_halim's code placed in edit and I didn't find there something like c_rev = 0. Can someone explain me a bit more that part in the method Reduce cost.

Having found the successive shortest path we need to update node potentials. For each i in V the potential pi_i is equal to the length of the shortest paths from s to t.

Is this mistyping or there really should be t? If there should be t, please, someone explain me why.

Thank you.
Re: What is the meaning of potential? (response to post by jbernadas) | Reply
Please, someone explain me how I should update costs and potentials if I find negative cycle with BellmannFord? Thank you.
Re: What is the meaning of potential? (response to post by boba5551) | Reply
If you find a negative cycle with Bellmann Ford then you have to augment all possible flow through that cycle, and then try again.
Re: What is the meaning of potential? (response to post by jbernadas) | Reply
I am not sure I have understand, so please explain me on the example below?
start_vertex end_vertex capacity cost
0 1 10 0
1 2 5 -7
2 3 5 -7
3 4 5 -7
4 5 10 0
4 1 5 2

s is vertex 0; t is vertex 5
How I should update costs and potentials after Bellmann Ford? What I should do before start using Dijkstra?
Thanks.
Re: What is the meaning of potential? (response to post by boba5551) | Reply
First you try to run Bellmann Ford, but you find a negative cycle (1->2->3->4->1 with cost -19), so you augment through that cycle as much as you can (it reduces the cost, so it is good). The remaining graph is:


0 1 10 0
2 1 5 7 <---+
3 2 5 7 <---+
4 3 5 7 <---+---- (1)
4 5 10 0 |
1 4 5 -2 <---+

flow: 0, cost: -95


The edges marked with (1) are the reverse links of those we used to augment the cycle. Now, the graph have no negative cycles, so the initial potentials are:


w={0, 0, 12, 5, -2, -2}


From now on you can use Disjktra with these weights to calculate the shortest paths. The final answer is flow=5, cost=-105.
[ 1 2 ]    NEXT >

RSS