[Lemon-user] Path decomposition and identification of flows

[Kovács Péter]

Hi Dimitris,

Yes, both procedures suggested by Alpár are capable of finding flows 
consisting of multiple paths.

Of course, there may be several feasible decomposition of the flow y 
into flows x_i, where y = x_1 + x_2 + ... + x_k.

For example,

Arc	y
1->2	10
2->4	10
1->3	10
3->4	10
4->5	15
4->6	5

And there are two commodities: 1 to 5 and 1 to 6. Then |x_1| = 15 and 
|x_2| = 5 and the x_i values are exactly determined on the arcs 4->5 and 
4->6, but they are ambiguous on the other four arcs. Both methods 
suggested by Alpár would determine a feasible solution, but not 
necessarily the same one.

I hope these help. Let us know if I understood something wrong.

Regards,
Péter



2015.04.01. 19:44 keltezéssel, Dimitris Paraskevopoulos írta:
> Dear all,
>
> May I refer to the query below:
>
> http://lemon.cs.elte.hu/pipermail/lemon-user/2010-October/000287.html
>
> ...and ask you what if we had a flow that starts from s, and before
> reaching t, has split and follows two parallel paths for a while and
> then meets at t.
>
> For example, lets say we have a flow of 10 units from node 1 to node 7.
> Here are some possible flows:
>
> Node 1 -Node 2: 10 units flow. then:
> Node 2-Node 3: 5 units
> Node 3-node 4:5 units
> Node 4-Node 7:5 units and...
>
>
> Node 2-Node 6:5 units
> Node 6-Node 7:5 units
>
> With 2-3-4-7 and 2-6-7 two parallel paths that start from Node 2 and end
> at node 7.
>
> Will the following procedure (posted by Alpár) identify the parallel
> flows of this commodity?
>
> * Repeat the following for each destination t.
>               * Find a maximum s-t flow x_t with y[e] as the capacity of
>                 e for each arc e.
>               * Decrease y by x_t. (i.e. y[e]:=y[e]-x_t[e] for each arc e)
>
> As with the case of Aran (link given above), I have different commodity
> flows with s-t and k, and I would like to know which arcs were used by
> each commodity, when solving the MCF.
>
> Any solution that would solve my problem, is greatly appreciated.
>
> Many thanks!
>
> Dimitris
>
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>