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.
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).
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?
Respuestas:
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/
fuente