Algoritmo rápido para el problema de coincidencia bipartita ponderada

8

Tengo un conjunto de agentes y un conjunto de n tareas, y necesito asignar a cada agente exactamente una tarea de manera que se minimice el costo. Algunos agentes son incompatibles con algunas tareas.nortenorte

Tengo una implementación del algoritmo húngaro que tarda aproximadamente un minuto en resolver mi matriz . Para las tareas prohibidas, establezco el costo en . ( Siempre existe una solución factible en mi problema).640×640

También lo configuré como un programa binario en CPLEX, que tarda unos 9 segundos en resolver el mismo problema. El modelo BIP excluye directamente las tareas prohibidas al omitir esas variables.

Todavía no he investigado configurarlo como un modelo de red en CPLEX, pero ese será probablemente mi próximo paso. Sin embargo, existe un costo de rendimiento al comunicarse con CPLEX, por lo que estoy seguro de que un algoritmo dedicado debería obtener un mejor rendimiento.

Este problema de coincidencia bipartita es un núcleo dentro de otro algoritmo de búsqueda iterativo, por lo que debe ejecutarse lo más rápido posible .

¿Hay algún algoritmo que pueda implementar que supere el algoritmo húngaro en este caso? ¿O tiene alguna otra sugerencia sobre cómo puedo mejorar el rendimiento de este kernel?

Ozzah
fuente
Solo como una nota al margen, la coincidencia bipartita es muy relevante para el flujo máximo mínimo, y como veo parece que tiene una situación dinámica y su gráfico original tal vez no cambie demasiado en dos iteraciones consecutivas, por lo que tal vez pueda encontrar algo relevante para su trabajo en línea con esta pregunta y respuesta .
Saeed
@Saeed, gracias, había considerado representarlo como una red de costo mínimo utilizando la información de la iteración anterior como una solución inicial factible.
Ozzah

Respuestas:

7

Puede probar uno de los algoritmos basados ​​en subastas para coincidencias bipartitas. (Ver, por ejemplo, notas de la conferencia que describen una variante simple aquí: https://staff.fnwi.uva.nl/nswalton/Notes/Bertsekas_Auction.pdf pero son posibles más optimizaciones).

Estos algoritmos no necesariamente tienen el mejor tiempo de ejecución en el peor de los casos, pero requieren solo operaciones muy simples, por lo que a menudo son eficientes en la práctica y son susceptibles de paralelización. (Y se pueden usar como base para recuperar los tiempos de ejecución más desfavorables más conocidos, ver: http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/

Aaron Roth
fuente