[Lemon-user] Path decomposition and identification of flows

[Dimitris Paraskevopoulos]

Hi Peter and everyone,

Many thanks for your reply. I 'll have to try this first, I got your point. I don't mind having one feasible solution among the infinite, maybe.

I tried to solve the attached problem with NetworkSimplex and I am getting strange results. 

I am using 

for (ListDigraph::ArcIt a(g); a != INVALID; ++ a) 
				fprintf(pF,"Arc %d %d\n",g.id(a),ns.flow(a));

to get the flows, however when I solve the associated LP with cplex I get completely different results, attached as well. 

Am I missing sth in the solution process or in the printing of the results?

Many thanks!

Dimitris 
 
________________________________________
From: Kovács Péter <kpeter at inf.elte.hu>
Sent: 10 April 2015 21:20
To: Dimitris Paraskevopoulos; lemon-user at lemon.cs.elte.hu
Subject: Re: [Lemon-user] Path decomposition and identification of flows

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
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: dimitris64.dim
Type: application/octet-stream
Size: 437 bytes
Desc: dimitris64.dim
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150415/5160af82/attachment-0001.obj>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Lemon solution.txt
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150415/5160af82/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: cplex solution.txt
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150415/5160af82/attachment-0003.txt>