[Lemon-user] Path decomposition and identification of flows

Sun Apr 19 22:28:57 CEST 2015

Hi Peter,

Many thanks for your immediate reply. CPLEX seems to give an optimum and even manually you can find a feasible solution:

8 units of flow in the path 1	2	3	4	5	6	7
7 units of flow in the path 10	7	8	9	1	2	3

the capacities of the arcs are 71 in all cases, apart from the 9-1 arc which is 7 and it is fine. 

I am so sorry, I might have misunderstood sth or I missed sth? 

Best wishes,

Dimitris

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

Hi Dimitris,

It seems that your example does not have a feasible solution.

When you run the Network Simplex algorithm, you should check the return
value of its run() function. For more information, see:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00276.html#a591276ea8f1afbe9d24bd1c1d48b0f53

As far as I see, the result of CPLEX is also infeasible. Could you
double-check it?

Regards,
Peter

2015.04.19. 21:34 keltezéssel, Dimitris Paraskevopoulos írta:
> 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, thenyou 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 Iget 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 node7.
>>>> 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 andend
>>>> 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
>>

_______________________________________________
Lemon-user mailing list
Lemon-user at lemon.cs.elte.hu
http://lemon.cs.elte.hu/mailman/listinfo/lemon-user