Problema de asignación

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Problema de optimización combinada

Ejemplo trabajado de asignar tareas a un número desigual de trabajadores utilizando el método húngaro

El problema de asignación es un problema fundamental de optimización combinatoria. En su forma más general, el problema es el siguiente:

La instancia del problema tiene una serie de agentes y varios tareas. Cualquier agente puede ser asignado para realizar cualquier tarea, incurriendo en algunos Costo que puede variar dependiendo de la asignación de agente-tarea. Es necesario realizar tantas tareas como sea posible asignando a la mayoría de un agente a cada tarea y en la mayoría de una tarea a cada agente, de tal manera que la Costo total de la asignación se minimiza.

Alternativamente, describiendo el problema usando la teoría de grafos:

El problema de asignación consiste en encontrar, en un gráfico bipartito ponderado, una combinación de un tamaño dado, en el que la suma de pesos de los bordes es mínima.

Si los números de agentes y tareas son iguales, entonces el problema se denomina asignación equilibrada. De lo contrario, se denomina asignación desequilibrada. Si el costo total de la asignación de todas las tareas es igual a la suma de los costos de cada agente (o la suma de los costos de cada tarea, que es lo mismo en este caso), entonces el problema se llama asignación lineal. Comúnmente, cuando se habla del problema de asignación sin ninguna calificación adicional, entonces se quiere decir problema de asignación balanceada lineal.

Ejemplos

Suponga que una empresa de taxis tiene tres taxis (los agentes) disponibles y tres clientes (las tareas) que desean ser recogidos lo antes posible. La empresa se enorgullece de las rápidas recolecciones, por lo que para cada taxi el "costo" de recoger a un cliente en particular dependerá del tiempo que tarde el taxi en llegar al punto de recogida. Este es un problema de asignación balanceada. Su solución es cualquier combinación de taxis y clientes que resulte en el menor costo total.

Ahora, suponga que hay cuatro taxis disponibles, pero todavía solo tres clientes. Este es un problema de asignación desequilibrada. Una forma de resolverlo es inventar una cuarta tarea ficticia, quizás llamada 'sentarse quieto sin hacer nada', con un costo de 0 para el taxi asignado. Esto reduce el problema a un problema de asignación equilibrada, que luego se puede resolver de la manera habitual y aún así dar la mejor solución al problema.

Se pueden realizar ajustes similares para permitir más tareas que agentes, tareas a las que se deben asignar múltiples agentes (por ejemplo, un grupo de más clientes de los que caben en un taxi) o maximizar las ganancias en lugar de minimizar los costos.

Definición formal

La definición formal del problema de asignación (o problema de asignación lineal) es

Dados dos sets, A y T, de igual tamaño, junto con una función de peso C: A × T → R. Encuentra una bijeción f: A → T tal que la función de costo:

sum _{{ain A}}C(a,f(a))

se minimiza.

Por lo general, la función de peso se ve como una matriz cuadrada de valor real C, por lo que la función de costo se escribe como:

sum _{{ain A}}C_{{a,f(a)}}

El problema es "lineal" porque la función de costo a optimizar, así como todas las restricciones, contienen solo términos lineales.

Algoritmos

Una solución ingenua para el problema de asignación es verificar todas las asignaciones y calcular el costo de cada una. Esto puede ser muy ineficiente ya que, con n agentes y n tareas, ¡hay n! (factorial de n) asignaciones diferentes. Afortunadamente, existen muchos algoritmos para resolver el problema en tiempo polinomial en n.

El problema de asignación es un caso especial del problema de transporte, que es un caso especial del problema de flujo de costo mínimo, que a su vez es un caso especial de un programa lineal. Si bien es posible resolver cualquiera de estos problemas utilizando el algoritmo simplex, cada especialización tiene un espacio de solución más pequeño y, por lo tanto, algoritmos más eficientes diseñados para aprovechar su estructura especial.

Asignación equilibrada

En el problema de asignación balanceada, ambas partes del gráfico bipartito tienen el mismo número de vértices, denotados por n.

Uno de los primeros algoritmos polinomio-tiempo para una asignación equilibrada fue el algoritmo húngaro. Es una mundial algoritmo – se basa en mejorar una combinación a lo largo de caminos crecientes (carriles alternativos entre vértices inigualables). Su complejidad de tiempo de ejecución, al utilizar los montones de Fibonacci, es ${displaystyle O(mn+n^{2}log n)}$ , donde m es un número de bordes. Este es el tiempo de funcionamiento más rápido de un algoritmo fuertemente polinomio para este problema. Si todos los pesos son enteros, entonces el tiempo de ejecución se puede mejorar para ${displaystyle O(mn+n^{2}log log n)}$ , pero el algoritmo resultante es sólo débilmente polinomial. Si los pesos son enteros, y todos los pesos son al máximo C (donde) C√1 es un poco entero), entonces el problema se puede resolver en ${displaystyle O(m{sqrt {n}}log(ncdot C))}$ tiempo débil-político en un método llamado Escalada de peso.

Además de los métodos globales, existen métodos locales que se basan en encontrar actualizaciones locales (en lugar de rutas de aumento completas). Estos métodos tienen peores garantías de tiempo de ejecución asintóticos, pero a menudo funcionan mejor en la práctica. Estos algoritmos se denominan algoritmos de subasta, algoritmos de trabajo de empuje o algoritmos de pre-flujo. Se demostró que algunos de estos algoritmos son equivalentes.

Algunos de los métodos locales suponen que el gráfico admite una coincidencia perfecta ; Si este no es el caso, entonces algunos de estos métodos podrían funcionar para siempre. Una forma técnica simple de resolver este problema es extender el gráfico de entrada a un gráfico bipartito completo, agregando bordes artificiales con pesas muy grandes. Estos pesos deben exceder los pesos de todas las coincidencias existentes, para evitar la aparición de bordes artificiales en la posible solución.

Como muestra Mulmuley, Vazirani y Vazirani, el problema de la combinación perfecta de peso mínimo se convierte en encontrar menores en la matriz de adyacencia de un gráfico. Usando el lema de aislamiento, un peso mínimo perfecto que coincide en un gráfico se puede encontrar con probabilidad al menos 1.2. Para un gráfico con n vértices, requiere ${displaystyle O(log ^{2}(n))}$ tiempo.

Asignación desequilibrada

En el problema de asignación no balanceada, la parte más grande del grafo bipartito tiene n vértices y la parte más pequeña tiene r<n vértices. También hay una constante s que es como máximo la cardinalidad de una coincidencia máxima en el gráfico. El objetivo es encontrar una coincidencia de costo mínimo de tamaño exactamente s. El caso más común es el caso en el que el gráfico admite una coincidencia perfecta unilateral (es decir, una coincidencia de tamaño r), y s=r .

La asignación desequilibrada puede reducirse a una asignación equilibrada. La reducción ingenua es añadir $n-r$ nuevos vértices a la parte más pequeña y conectarlos a la parte más grande utilizando bordes de coste 0. Sin embargo, esto requiere ${displaystyle n(n-r)}$ nuevos bordes. Una reducción más eficiente se llama la técnica de duplicación. Aquí, un nuevo gráfico G ' está construido a partir de dos copias del gráfico original G: una copia adelante Gf y una copia atrasada Gb. La copia atrasada es "golpeada", por lo que, en cada lado G ', hay ahora n+r vertices. Entre las copias, necesitamos añadir dos tipos de bordes de enlace:

Grande-a-grande: de cada vértice en la parte más grande de Gf, añadir un borde de cero costo al vértice correspondiente en Gb.
Small-to-small: si el gráfico original no tiene una coincidencia de un lado-perfecto, entonces de cada vértice en la parte más pequeña de Gf, añadir un borde de muy alto costo al vértice correspondiente en Gb.

Todo en absoluto, al menos $n+r$ Se requieren nuevos bordes. El gráfico resultante siempre tiene una combinación perfecta de tamaño $n+r$ . Un coste mínimo perfecto en este gráfico debe consistir en los emparejamientos de máxima-cardialidad de coste mínimo en Gf y Gb. El principal problema con esta técnica de duplicación es que no hay ganancia de velocidad cuando ${displaystyle rll n}$ .

En lugar de utilizar la reducción, el problema de asignación desequilibrada puede resolverse generalizando directamente los algoritmos existentes para una asignación equilibrada. El algoritmo húngaro se puede generalizar para resolver el problema en ${displaystyle O(ms+s^{2}log r)}$ Tiempo de polinomía. En particular, si s=r entonces el tiempo de ejecución es ${displaystyle O(mr+r^{2}log r)}$ . Si los pesos son enteros, entonces el método de Thorup se puede utilizar para obtener un tiempo de funcionamiento ${displaystyle O(ms+s^{2}log log r)}$ .

Solución por programación lineal

El problema de la asignación se puede resolver presentando como un programa lineal. Para comodidad presentaremos el problema de maximización. Cada borde $() i, j)$ , donde i está en A y j está en T, tiene un peso ${textstyle w_{ij}}$ . Para cada borde $(i,j)$ tenemos una variable ${textstyle x_{ij}}$ _. La variable es 1 si el borde está contenido en el emparejado y 0 de otro modo, por lo que establecemos las limitaciones de dominio:

{displaystyle 0leq x_{ij}leq 1{text{ for }}i,jin A,T,,}

{displaystyle x_{ij}in mathbb {Z} {text{ for }}i,jin A,T.}

El peso total del juego es: ${displaystyle sum _{(i,j)in Atimes T}w_{ij}x_{ij}}$ . El objetivo es encontrar una combinación perfecta de peso máximo.

Para garantizar que las variables realmente representen una coincidencia perfecta, agregamos restricciones que dicen que cada vértice es adyacente a exactamente un borde en la coincidencia, es decir,

{displaystyle sum _{jin T}x_{ij}=1{text{ for }}iin A,,~~~sum _{iin A}x_{ij}=1{text{ for }}jin T,,}

En total tenemos el siguiente LP:

{displaystyle {text{maximize}}~~sum _{(i,j)in Atimes T}w_{ij}x_{ij}}

{displaystyle {text{subject to}}~~sum _{jin T}x_{ij}=1{text{ for }}iin A,,~~~sum _{iin A}x_{ij}=1{text{ for }}jin T}

{displaystyle 0leq x_{ij}leq 1{text{ for }}i,jin A,T,,}

{displaystyle x_{ij}in mathbb {Z} {text{ for }}i,jin A,T.}

Otros métodos y algoritmos de aproximación

Existen otros enfoques para el problema de asignación y Duan y Pettie los revisan (consulte la Tabla II). Su trabajo propone un algoritmo de aproximación para el problema de asignación (y el problema de coincidencia de peso máximo más general), que se ejecuta en tiempo lineal para cualquier límite de error fijo.

Generalización

Cuando se expresa como un problema de teoría de grafos, el problema de asignación puede extenderse de gráficos bipartitos a gráficos arbitrarios. El problema correspondiente, de encontrar una coincidencia en un gráfico ponderado donde la suma de los pesos se maximiza, se denomina problema de coincidencia de peso máximo.

Otra generalización del problema de asignación es ampliar el número de conjuntos que se emparejarán de dos a muchos. Entonces, en lugar de hacer coincidir los agentes con las tareas, el problema se extiende a hacer coincidir los agentes con las tareas, los intervalos de tiempo y las ubicaciones. Esto da como resultado un problema de asignación multidimensional (MAP).

Referencias y lecturas adicionales

^ a b c d Lyle Ramshaw, Robert E. Tarjan (2012). "En asignaciones de coste mínimo en gráficos bipartitos desequilibrados" (PDF). Laboratorios de investigación HP.
^ Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms". J. ACM. 34 (3): 596-615. doi:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.
^ Thorup, Mikkel (2004-11-01). "Las colas de prioridad entero con la clave de disminución en tiempo constante y el problema de los caminos más cortos de una sola fuente". Journal of Computer and System Sciences. Special Issue on STOC 2003. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003. ISSN 0022-0000.
^ Gabow, H.; Tarjan, R. (1989-10-01). "Los algoritmos de escala rápida para problemas de red". SIAM Journal on Computing. 18 (5): 1013-1036. doi:10.1137/0218069. ISSN 0097-5397.
^ Goldberg, A.; Kennedy, R. (1997-11-01). "Global Price Updates Help". SIAM Journal on Discrete Mathematics. 10 (4): 551–572. doi:10.1137/S0895480194281185. ISSN 0895-4801.
^ Orlin, James B.; Ahuja, Ravindra K. (1992-02-01). "Nuevos algoritmos de escalada para la asignación y problemas mínimos del ciclo medio". Programación matemática. 54 (1–3): 41–56. doi:10.1007/BF01586040. ISSN 0025-5610. S2CID 18213947.
^ Alfaro, Carlos A.; Pérez, Sergio L.; Valencia, Carlos E.; Vargas, Marcos C. (2022-06-01). "El problema de la asignación revistió". Cartas de optimización. 16 (5): 1531–1548. doi:10.1007/s11590-021-01791-4. ISSN 1862-4480.
^ Mulmuley, Ketan; Vazirani, Umesh; Vazirani, Vijay (1987). "La adquisición es tan fácil como la inversión de matriz". Combinatorica. 7 (1): 105–113. doi:10.1007/BF02579206. S2CID 47370049.
^ Duan, Ran; Pettie, Seth (2014-01-01-01). "Aproximación en tiempo-lineal para la combinación de peso máximo" (PDF). Journal of the ACM. 61: 1–23. doi:10.1145/2529989. S2CID 207208641.

Contenido relacionado

Más resultados...