Problemas del algoritmo de Munkres para asignación no estándar

Question

Tengo una variación del problema de asignación que el algoritmo habitual Munkres/húngaro parece estar mal equipado para resolver.

En el problema de asignación tradicional, hay n trabajadores que deben asignarse a n trabajos, y una matriz que contiene el costo de asignar cada trabajador a cada trabajo.

En esta variación, solo tenemos m (m < n) trabajadores. Como el algoritmo de Munkres requiere un número igual de trabajadores y trabajos, creamos (n - m) trabajadores "ficticios" que pueden asignarse a los trabajos de repuesto. Además, los trabajos mismos están organizados en una gran cantidad de categorías discretas.

Nos gustaría imponer la restricción de que al menos 1 trabajo de cada categoría se asigna a un trabajador real (no simulado). Esto es difícil de hacer elegantemente: puede, por ejemplo, elegir un trabajo aleatorio de cada categoría y desinflar artificialmente cada costo asociado al trabajador real, pero esta es una solución muy cruda que compromete severamente la integridad de la tarea final.

Lo que hacemos actualmente es ejecutar el algoritmo varias veces, evaluando cada vez la asignación de salida y luego modificando la matriz de costos de modo que los costos para todos los trabajos en cualquier categoría que se asignaron solo a los trabajadores ficticios se reduzcan ligeramente. Esto funciona adecuadamente, pero para conjuntos de datos moderadamente grandes (n ~ = 500) el proceso puede tardar un tiempo (cada tarea de Munkres toma quizás 10 segundos para computarse, y con suficientes categorías puede haber un número no trivial de iteraciones).

¿Hay algún algoritmo modificado de Munkres, o un algoritmo completamente diferente, que resuelva este problema de manera más eficiente?

Answer 1

¿Están las categorías disjustadas? ¿Cada trabajo tiene exactamente una categoría? Entonces, ¿qué hay de flujo de costo mínimo?

tipos de nodos:

SRC - source 
SNK - sink 
C - a node or each category 
J - a node for each job 
W - a node for each worker 

las conexiones:

1) from SRC to C, capacity 1, cost 0 
2) from SRC to C, capacity infinite, cost a high number 
3) from C to J, capacity 1, cost 0 
4) from J to W, capcity 1, the cost of job J done by worker W 
5) from W to SNK, cost 0, capacity 1 

A continuación, el algoritmo va a llenar enlaces de tipo 1 en primer lugar, lo que significa cada categoría obtendrá al menos un trabajador (si es posible).