Eu tenho um conjunto de agentes e um conjunto de n tarefas, e preciso atribuir cada agente a exatamente uma tarefa, para que o custo seja minimizado. Alguns agentes são incompatíveis com algumas tarefas.
Eu tenho uma implementação do algoritmo húngaro que leva cerca de um minuto para resolver para o meu matriz. Para tarefas proibidas, defino o custo para ∞ . ( Sempre existe uma solução viável no meu problema).
Também o configurei como um programa binário no CPLEX, que leva cerca de 9 segundos para resolver o mesmo problema. O modelo BIP exclui atribuições proibidas imediatamente, omitindo essas variáveis.
Ainda não investiguei a configuração como um modelo de rede no CPLEX, mas esse provavelmente será o meu próximo passo. Há, no entanto, um custo de desempenho na comunicação com o CPLEX, portanto, tenho certeza de que um algoritmo dedicado deve obter melhor desempenho.
Esse problema de correspondência bipartida é um kernel dentro de outro algoritmo de pesquisa iterativo; portanto, ele deve ser executado o mais rápido possível .
Existe algum algoritmo que eu possa implementar que superará o algoritmo húngaro nesse caso? Ou você tem outras sugestões sobre como posso melhorar o desempenho deste kernel?
Respostas:
Você pode tentar um dos algoritmos baseados em leilão para correspondências bipartidas. (Veja, por exemplo, notas de aula que descrevem uma variante simples aqui: https://staff.fnwi.uva.nl/nswalton/Notes/Bertsekas_Auction.pdf, mas são possíveis mais otimizações).
Esses algoritmos não têm necessariamente o melhor tempo de execução no pior dos casos, mas requerem operações muito simples e, portanto, geralmente são eficientes na prática e são passíveis de paralelização. (E eles podem ser usados como base para recuperar os tempos de execução dos piores casos mais conhecidos, consulte: http://agtb.wordpress.com/2009/07/07/13/auction-algorithm-for-bipartite-matching/
fonte