[Lemon-user] Path decomposition and identification of flows

[Kovács Péter]

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
>>
>