[Lemon-user] Path decomposition and identification of flows

Kovács Péter kpeter at inf.elte.hu
Mon Apr 20 00:38:18 CEST 2015 

Hi Dimitris,

I see now: be aware of the sign of supply/demand values. The DIMACS 
format as well as the algorithms in LEMON work with _supply_ values, 
i.e. positive values for supply nodes and negative values for demand 
nodes. See definitions here:
http://lemon.cs.elte.hu/pub/doc/1.3.1/a00010.html
and the description of DIMACS format here:
http://lpsolve.sourceforge.net/5.5/DIMACS_mcf.htm

However, according to the solution you sent, your .dim file actually 
contains demand values. If you replace each of these values with its 
opposite, then your file becomes feasible. Your CPLEX-based code should 
also be adjusted accordingly.

Regards,
Péter


2015.04.19. 22:28 keltezéssel, Dimitris Paraskevopoulos írta:
> 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
>

More information about the Lemon-user mailing list