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?