8
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Aug 12, 2014 at 12:37
  • $\begingroup$ @Saeed, thanks, I had considered representing it as a min cost network using the information from the previous iteration as an initial feasible solution. $\endgroup$
    – Ozzah
    Commented Aug 14, 2014 at 2:26

1 Answer 1

Reset to default
7
$\begingroup$

You might try one of the auction-based algorithms for bipartite matchings. (See e.g. lecture notes describing a simple variant here: https://staff.fnwi.uva.nl/n.s.walton/Notes/Bertsekas_Auction.pdf but more optimizations are possible).

These algorithms do not necessarily have the best worst-case running time, but require only very simple operations, and so are often efficient in practice, and are amenable to parallelization. (And they can be used as a basis for recovering the best known worst case running times, see: http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.