# Fast algorithm for weighted bipartite matching problem

I have a set of $n$ agents and a set of $n$ tasks, and I need to assign each agent to exactly one task such that a cost is minimised. Some agents are incompatible with some tasks.

I have an implementation of the Hungarian Algorithm which takes about a minute to solve for my $640 \times 640$ matrix. For forbidden assignments, I set the cost to $\infty$. (There always exists a feasible solution in my problem).

I've also set it up as a binary program in CPLEX, which takes about 9 seconds to solve for the same problem. The BIP model excludes forbidden assignments outright by omitting those variables.

I haven't yet investigated setting it up as a networking model in CPLEX, but that will likely be my next step. There is, however, a performance cost with communicating with CPLEX, so I'm sure a dedicated algorithm should get better performance.

This bipartite matching problem is a kernel within another iterative search algorithm, so it must run as fast as possible.

Are there any algorithms that I can implement that will outperform the Hungarian Algorithm in this case? Or do you have any other suggestions on how I can improve the performance of this kernel?

• Just as a side note, the bipartite matching is highly relevant to minimum maximum flow, and as I see seems you have a dynamic situation and your original graph maybe does not change too much in two consecutive iterations, so perhaps you can find something relevant to your work along line of this question and answer. Aug 12 '14 at 12:37
• @Saeed, thanks, I had considered representing it as a min cost network using the information from the previous iteration as an initial feasible solution. Aug 14 '14 at 2:26