[Lemon-user] Path decomposition and identification of flows

[Dimitris Paraskevopoulos]

Hi Peter, 

Thank you for your reply. I appreciate the fact that the MCF may have multiple optima, however in my example the supply/demand constraints are not satisfied (in the solution got from Lemon) and cplex gets a much larger obj value than Lemon. I suspect it is sth wrong with my input process? I went into the source code of readimacs and it seems that it gets the right data. 

I very much look fwd to hearing from you and many thanks once again,

Best wishes,

Dimitris 


Sent from my iPad

> On 19 Apr 2015, at 20:24, Kovács Péter <kpeter at inf.elte.hu> wrote:
> 
> Hi Dimitris,
> 
> A flow problem may have several completely different optimal solutions. It is not strange that different algorithms find different results.
> 
> However, if you are not sure whether both results are optimal flows, you can check them as follows:
> 
> 1. Check feasibility:
> - flow values do not violate capacity bounds on the arcs
> - supply/demand constraints are satisfied for each node
> 
> 2. Check optimality:
> - If the two algorithms provide flows having the same total cost, then you can safely assume that both are optimal.
> - However, all min-cost flow algorithms in LEMON also provide the so-called dual solution (node potentials), which can be used for validating their optimality. See:
> http://lemon.cs.elte.hu/pub/doc/1.3.1/a00010.html
> 
> Regards,
> Peter
> 
> 
> 
>> 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
>