[Lemon-user] MCF Optimal Assignment problem

[T.A. Heba Essam]

Dear Peter, 

Thanks, The LEQ supply type solved the problem easily.

Best regards, 
Heba
________________________________________
From: Kovács Péter <kpeter at inf.elte.hu>
Sent: Wednesday, May 21, 2014 7:51 AM
To: T.A. Heba Essam
Cc: lemon-user at lemon.cs.elte.hu
Subject: Re: [Lemon-user] MCF Optimal Assignment problem

Dear Heba,

The attached code example shows how to use NetworkSimplex with LEQ
supply type to solve the example you have sent.

In fact, your idea of adding fake destination nodes would also work, but
the attached code is by far the easiest solution.

Regards,
Peter




On 2014.05.21. 7:50, T.A. Heba Essam wrote:
> Dear Peter,
>
> First of all, thanks a lot for your prompt response and help. I'm grateful for the LEMON community's endless co-operation.
>
> Yes, you did interpret the problem perfectly and I'll be trying either solutions and feeding you back soon.
>
> Moreover, I was thinking if I added fake (K - L) destination nodes (which makes L = K), set the demand value of each destination node to -1 and all input arcs to additional fake nodes have cost of 0. Would this solve the problem? I was about to try it and check the behavior. However, the solutions you provided seem more reasonable and easier.
>
> Finally, could you please provide me with an example of how to set the supplyType to LEQ. I tried many statements but they're giving me errors.
>
> Thanks & best regards,
> Heba
>
> ________________________________________
> From: Kovács Péter <kpeter at inf.elte.hu>
> Sent: Tuesday, May 20, 2014 9:12 PM
> To: T.A. Heba Essam; lemon-user at lemon.cs.elte.hu
> Subject: Re: [Lemon-user] MCF Optimal Assignment problem
>
> Dear Heba,
>
> The min-cost flow algorithms can be used to solve your problem, but you
> should formulate the problem correctly.
>
> As far as I understand, you have a directed bipartite graph with K
> source nodes and L destination nodes and K > L. The capacity values are
> uniformly set to 1 on the arcs. You have used an MCF algorithm to find
> an optimal flow consisting of K arcs and tried to select L from these K
> arcs. However, you would actually require an optimal flow of L arcs
> instead. (Only L of the K source nodes should be used, but you do not
> know in advance, which ones.)
>
> Do I interpret your problem correctly? If yes, then you can solve this
> with MCF algorithms easily.
>
> 1. The first solution is to modify your graph in order to formulate your
> actual problem as a usual min-cost flow problem:
>          - add an extra source node s;
>          - set the supply value of s to L (2 in your example);
>          - for each original source node u, add an arc from s to u with capacity 1;
>          - set the supply value of each original source node to 0;
>          - set the supply value of each destination node to -1 (not -2 as in
> your example).
>
> On this modified graph, a min-cost flow will actually carry L amount of
> flow from s to the L destination nodes. Such a flow will use L distinct
> arcs and L distinct source nodes of the original graph, and they will be
> selected in an optimal way (with minimal total cost).
>
> 2. You can even skip the above transformation if you use the
> NetworkSimplex class, as it solves a more general form of the min-cost
> flow problem. That is, the sum of supply values need not be equal to the
> sum of demand values. You can use the so-called LEQ supply type to solve
> your problem directly, without adding new nodes or arcs, but you should
> set the supply of each source node to 1 and the supply of each
> destination node to -1. For more information, see:
> http://lemon.cs.elte.hu/pub/doc/1.3/a00005.html
> http://lemon.cs.elte.hu/pub/doc/1.3/a00269.html
>
>
> I hope this helps.
>
> Best regards,
> Peter
>
>
> On 2014.05.20. 15:12, T.A. Heba Essam wrote:
>> Dears,
>>
>>
>> I have a scientific question more than a technical one. I need to get an
>> optimal assignment when the number of source nodes is greater than the
>> number of destination nodes. I'm currently using MCF solver, it gets me
>> an optimal solution when the number of source and destination nodes is
>> equal. Otherwise, it might not be optimal.
>>
>>
>> Is there something I should handle? or I should be using another
>> algorithm to solve this problem?
>>
>>
>> Please find attachment for more clarification. It illustrates an
>> example which I encountered while testing.
>>
>>
>> Thanks,
>>
>> Heba
>>
>>
>>
>>
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>>