[Lemon-user] MCF Optimal Assignment problem

[Kovács Péter]

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
>