Problema de asignación

Problema de optimización combinatoria

Ejemplo práctico de asignación de tareas a un número desigual de trabajadores utilizando el método húngaro

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

La instancia del problema tiene un número de agentes y un número de tareas . Cualquier agente puede ser asignado para realizar cualquier tarea, incurriendo en algún costo que puede variar dependiendo de la asignación agente-tarea. Se requiere realizar tantas tareas como sea posible asignando como máximo un agente a cada tarea y como máximo una tarea a cada agente, de tal manera que el costo total de la asignación sea mínimo.

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

El problema de asignación consiste en encontrar, en un grafo bipartito ponderado , un emparejamiento de un tamaño dado, en el que la suma de los pesos de las aristas sea mínima.

Si el número de agentes y tareas es igual, entonces el problema se denomina asignación balanceada . En caso contrario, se denomina asignación no balanceada . ^[1] Si el costo total de la asignación para todas las tareas es igual a la suma de los costos para cada agente (o la suma de los costos para cada tarea, que es lo mismo en este caso), entonces el problema se denomina asignación lineal . Comúnmente, cuando se habla del problema de asignación sin ninguna calificación adicional, entonces se hace referencia al problema de asignación balanceada lineal .

Ejemplos

Supongamos que una empresa de taxis tiene tres taxis (los agentes) disponibles y tres clientes (las tareas) que desean que los recojan lo antes posible. La empresa se enorgullece de sus recogidas rápidas, por lo que, para cada taxi, el "coste" 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 equilibrada . Su solución es la combinación de taxis y clientes que dé como resultado el menor coste total.

Ahora, supongamos que hay cuatro taxis disponibles, pero que todavía hay sólo tres clientes. Éste es un problema de asignación no balanceado . Una forma de resolverlo es inventar una cuarta tarea ficticia, tal vez llamada "quedarse quieto sin hacer nada", con un costo de 0 para el taxi que se le asigna. Esto reduce el problema a un problema de asignación balanceado, que luego puede resolverse 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 conjuntos, A y T , junto con una función de peso C  : A × T → R . Halla una biyección f  : A → T tal que la función de costo :

${\displaystyle \sum _{a\in A}C(a,f(a))}$

se minimiza.

Generalmente, la función de peso se considera como una matriz cuadrada de valores reales C , de modo que la función de costo se escribe como:

${\displaystyle \sum _{a\in A}C_{a,f(a)}}$

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

Algoritmos

Una solución ingenua para el problema de asignación es comprobar todas las asignaciones y calcular el coste de cada una. Esto puede resultar muy ineficiente ya que, con n agentes y n tareas, hay n ! ( factorial de n ) asignaciones diferentes.

Otra solución ingenua es asignar primero, con avidez, el par con el menor costo y eliminar los vértices; luego, entre los vértices restantes, asignar el par con el menor costo, y así sucesivamente. Este algoritmo puede dar como resultado una solución no óptima. Por ejemplo, supongamos que hay dos tareas y dos agentes con los siguientes costos:

• Alice: Tarea 1 = 1, Tarea 2 = 2.
• George: Tarea 1 = 5, Tarea 2 = 8.

El algoritmo codicioso asignaría la Tarea 1 a Alice y la Tarea 2 a George, por un costo total de 9; pero la asignación inversa tiene un costo total de 7.

Afortunadamente, existen muchos algoritmos para encontrar la asignación óptima en el 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 , o en el peor de los casos el tiempo polinomial utilizando el método del elipsoide , 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 equilibrada, ambas partes del gráfico bipartito tienen el mismo número de vértices, denotado por n .

Uno de los primeros algoritmos de tiempo polinomial para la asignación equilibrada fue el algoritmo húngaro . Es un algoritmo global : se basa en mejorar una correspondencia a lo largo de caminos de aumento (caminos alternativos entre vértices no coincidentes). Su complejidad en tiempo de ejecución, cuando se utilizan montículos de Fibonacci , es , ^[2] donde m es un número de aristas. Este es actualmente el tiempo de ejecución más rápido de un algoritmo fuertemente polinomial para este problema. Si todos los pesos son números enteros, entonces el tiempo de ejecución se puede mejorar a , pero el algoritmo resultante es solo débilmente polinomial. ^[3] Si los pesos son números enteros, y todos los pesos son como máximo C (donde C > 1 es algún número entero), entonces el problema se puede resolver en tiempo débilmente polinomial en un método llamado escalamiento de pesos . ^{[4] [5] [6]} ${\displaystyle O(mn+n^{2}\log n)}$ ${\displaystyle O(mn+n^{2}\log \log n)}$ ${\displaystyle O(m{\sqrt {n}}\log(n\cdot C))}$

Además de los métodos globales, existen métodos locales que se basan en la búsqueda de actualizaciones locales (en lugar de rutas de ampliación completas). Estos métodos tienen peores garantías de tiempo de ejecución asintótica, pero a menudo funcionan mejor en la práctica. Estos algoritmos se denominan algoritmos de subasta , algoritmos push-relabel o algoritmos preflow-push. Se ha demostrado que algunos de estos algoritmos son equivalentes. ^[7]

Algunos de los métodos locales suponen que el gráfico admite un emparejamiento perfecto ; si este no es el caso, entonces algunos de estos métodos podrían ejecutarse indefinidamente. ^{[1] : 3} Una forma técnica simple de resolver este problema es extender el gráfico de entrada a un gráfico bipartito completo, agregando aristas artificiales con pesos muy grandes. Estos pesos deben exceder los pesos de todos los emparejamientos existentes, para evitar la aparición de aristas artificiales en la posible solución.

Como lo demostraron Mulmuley, Vazirani y Vazirani, ^[8] el problema del emparejamiento perfecto de peso mínimo se convierte en encontrar menores en la matriz de adyacencia de un grafo. Usando el lema de aislamiento , un emparejamiento perfecto de peso mínimo en un grafo se puede encontrar con una probabilidad de al menos 1 ⁄ 2 . Para un grafo con n vértices, requiere tiempo. ${\displaystyle O(\log ^{2}(n))}$

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 un emparejamiento máximo en el grafo. El objetivo es encontrar un emparejamiento de costo mínimo de tamaño exactamente s . El caso más común es el caso en el que el grafo admite un emparejamiento perfecto unilateral (es decir, un emparejamiento de tamaño r ), y s = r .

La asignación no balanceada puede reducirse a una asignación balanceada. La reducción ingenua consiste en agregar nuevos vértices a la parte más pequeña y conectarlos a la parte más grande usando aristas de costo 0. Sin embargo, esto requiere nuevas aristas. Una reducción más eficiente se denomina técnica de duplicación . Aquí, se construye un nuevo grafo G' a partir de dos copias del grafo original G : una copia hacia adelante Gf y una copia hacia atrás Gb. La copia hacia atrás se "voltea", de modo que, en cada lado de G' , ahora hay n + r vértices. Entre las copias, necesitamos agregar dos tipos de aristas de enlace: ^{[1] : 4–6} ${\displaystyle n-r}$ ${\displaystyle n(n-r)}$

• De grande a grande: desde cada vértice en la parte más grande de Gf , agregue una arista de costo cero al vértice correspondiente en Gb .
• De pequeño a pequeño: si el gráfico original no tiene una correspondencia unilateral perfecta, entonces desde cada vértice en la parte más pequeña de Gf , agregue una arista de costo muy alto al vértice correspondiente en Gb .

En general, se requieren como máximo nuevos bordes. El grafo resultante siempre tiene una correspondencia perfecta de tamaño . Una correspondencia perfecta de costo mínimo en este grafo debe constar de correspondencias de cardinalidad máxima de costo mínimo en Gf y Gb. El problema principal con esta técnica de duplicación es que no hay ganancia de velocidad cuando . ${\displaystyle n+r}$ ${\displaystyle n+r}$ ${\displaystyle r\ll n}$

En lugar de utilizar la reducción, el problema de asignación desequilibrada se puede resolver generalizando directamente los algoritmos existentes para la asignación equilibrada. El algoritmo húngaro se puede generalizar para resolver el problema en tiempo fuertemente polinomial. En particular, si s = r entonces el tiempo de ejecución es . Si los pesos son números enteros, entonces se puede utilizar el método de Thorup para obtener un tiempo de ejecución de . ^{[1] : 6} ${\displaystyle O(ms+s^{2}\log r)}$ ${\displaystyle O(mr+r^{2}\log r)}$ ${\displaystyle O(ms+s^{2}\log \log r)}$

Solución por programación lineal

El problema de asignación se puede resolver presentándolo como un programa lineal . Para mayor comodidad, presentaremos el problema de maximización. Cada arista ( i , j ) , donde i está en A y j está en T, tiene un peso . Para cada arista ⁠ ⁠ tenemos una variable _. La variable es 1 si la arista está contenida en la coincidencia y 0 en caso contrario, por lo que establecemos las restricciones del dominio: ${\textstyle w_{ij}}$ ${\displaystyle (i,j)}$ ${\textstyle x_{ij}}$ $${\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}$$ $${\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}$$

El peso total de la correspondencia es: . El objetivo es encontrar una correspondencia perfecta con el peso máximo. ${\displaystyle \sum _{(i,j)\in A\times T}w_{ij}x_{ij}}$

Para garantizar que las variables realmente representan una coincidencia perfecta, agregamos restricciones que indican que cada vértice es adyacente a exactamente un borde en la coincidencia, es decir, . $${\displaystyle \sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T,\,}$$

En total tenemos el siguiente LP:

$${\displaystyle {\text{maximize}}~~\sum _{(i,j)\in A\times T}w_{ij}x_{ij}}$$ $${\displaystyle {\text{subject to}}~~\sum _{j\in T}x_{ij}=1{\text{ for }}i\in A,\,~~~\sum _{i\in A}x_{ij}=1{\text{ for }}j\in T}$$ $${\displaystyle 0\leq x_{ij}\leq 1{\text{ for }}i,j\in A,T,\,}$$ $${\displaystyle x_{ij}\in \mathbb {Z} {\text{ for }}i,j\in A,T.}$$Este es un programa lineal entero. Sin embargo, podemos resolverlo sin las restricciones de integralidad (es decir, eliminar la última restricción), utilizando métodos estándar para resolver programas lineales continuos. Si bien esta formulación también permite valores de variables fraccionarias, en este caso especial, el PL siempre tiene una solución óptima donde las variables toman valores enteros. Esto se debe a que la matriz de restricciones del PL fraccionario es totalmente unimodular  : satisface las cuatro condiciones de Hoffman y Gale.

Otros métodos y algoritmos de aproximación

Existen otros enfoques para el problema de asignación, que han sido analizados por Duan y Pettie ^[9] (véase la Tabla II). Su trabajo propone un algoritmo de aproximación para el problema de asignación (y el problema más general de correspondencia de peso máximo ), que se ejecuta en tiempo lineal para cualquier límite de error fijo.

Generalización

Cuando se lo formula como un problema de teoría de grafos, el problema de asignación se puede extender de grafos bipartitos a grafos arbitrarios. El problema correspondiente, de encontrar una correspondencia en un grafo ponderado donde la suma de pesos se maximiza, se denomina problema de correspondencia de peso máximo .

Otra generalización del problema de asignación es ampliar el número de conjuntos que se deben emparejar de dos a muchos. De modo que, en lugar de emparejar agentes con tareas, el problema se extiende a emparejar agentes con tareas con intervalos de tiempo con ubicaciones. Esto da como resultado el problema de asignación multidimensional (MAP) .

Véase también

• Algoritmo de subasta
• Problema de asignación generalizada
• Problema de asignación de cuello de botella lineal
• Problema de transporte de Monge-Kantorovich , una formulación más general
• Programa Nacional de Emparejamiento de Residentes
• Problema de asignación cuadrática
• Coincidencia de rango máximo
• Problema de secretaria
• Problema de matrimonio estable
• Problema de compañeros de piso estables
• Problema de asignación de objetivos de armas
• Problema de asignación de viviendas
• Problema de asignación multidimensional (MAP)

Referencias y lecturas adicionales

1. Lyle Ramshaw, Robert E. Tarjan (2012). "Sobre asignaciones de costo mínimo en grafos bipartitos no balanceados" (PDF) . Laboratorios de investigación de HP .
2. Fredman, Michael L.; Tarjan, Robert Endre (1 de julio de 1987). "Montones de Fibonacci y sus usos en algoritmos mejorados de optimización de redes". J. ACM . 34 (3): 596–615. doi : 10.1145/28869.28874 . ISSN  0004-5411. S2CID  7904683.
3. Thorup, Mikkel (1 de noviembre de 2004). "Colas de prioridad de enteros con clave decreciente en tiempo constante y el problema de las rutas más cortas de una sola fuente". Journal of Computer and System Sciences . Número especial sobre STOC 2003. 69 (3): 330–353. doi : 10.1016/j.jcss.2004.04.003 . ISSN  0022-0000.
4. Gabow, H.; Tarjan, R. (1989-10-01). "Algoritmos de escalamiento más rápido para problemas de red". Revista SIAM de Computación . 18 (5): 1013–1036. doi :10.1137/0218069. ISSN  0097-5397.
5. Goldberg, A.; Kennedy, R. (1997-11-01). "Ayuda para la actualización de precios globales". Revista SIAM de Matemáticas Discretas . 10 (4): 551–572. doi :10.1137/S0895480194281185. ISSN  0895-4801.
6. Orlin, James B.; Ahuja, Ravindra K. (1992-02-01). "Nuevos algoritmos de escalamiento para los problemas de asignación y de ciclo de media mínima". Programación matemática . 54 (1–3): 41–56. doi :10.1007/BF01586040. ISSN  0025-5610. S2CID  18213947.
7. Alfaro, Carlos A.; Pérez, Sergio L.; Valencia, Carlos E.; Vargas, Marcos C. (1 de junio de 2022). "El problema de asignación revisitado". Optimization Letters . 16 (5): 1531–1548. doi :10.1007/s11590-021-01791-4. ISSN  1862-4480. S2CID  238644205.
8. Mulmuley, Ketan ; Vazirani, Umesh ; Vazirani, Vijay (1987). "Hacer coincidir es tan fácil como invertir matrices". Combinatoria . 7 (1): 105-113. doi :10.1007/BF02579206. S2CID  47370049.
9. Duan, Ran; Pettie, Seth (1 de enero de 2014). "Aproximación de tiempo lineal para la correspondencia de peso máximo" (PDF) . Revista de la ACM . 61 : 1–23. doi :10.1145/2529989. S2CID  207208641.

• Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de matemáticas y sus aplicaciones. Vol. 108. Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4.Zbl 1106.05001  .
• Burkard, Rainer ; M. Dell'Amico; S. Martello (2012). Problemas de asignación (reimpresión revisada) . SIAM. ISBN 978-1-61197-222-1.
• Bertsekas, Dimitri (1998). Optimización de redes: modelos continuos y discretos . Athena Scientific. ISBN 978-1-886529-02-1.