Problema de asignación generalizada

Problema de optimización combinatoria

En matemáticas aplicadas , el problema de asignación generalizado máximo es un problema de optimización combinatoria . Este problema es una generalización del problema de asignación en el que tanto las tareas como los agentes tienen un tamaño. Además, el tamaño de cada tarea puede variar de un agente a otro.

Este problema en su forma más general es el siguiente: hay 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 y beneficio que puede variar dependiendo de la asignación de agente-tarea. Además, cada agente tiene un presupuesto y la suma de los costos de las tareas que se le asignan no puede exceder este presupuesto. Se requiere encontrar una asignación en la que todos los agentes no excedan su presupuesto y el beneficio total de la asignación sea máximo.

En casos especiales

En el caso especial en el que los presupuestos de todos los agentes y los costes de todas las tareas son iguales a 1, este problema se reduce al problema de asignación . Cuando los costes y beneficios de todas las tareas no varían entre los diferentes agentes, este problema se reduce al problema de la mochila múltiple. Si hay un solo agente, entonces, este problema se reduce al problema de la mochila .

Explicación de la definición

A continuación, tenemos n tipos de artículos, a través de y m tipos de contenedores a través de . Cada contenedor está asociado con un presupuesto . Para un contenedor , cada artículo tiene una ganancia y un peso . Una solución es una asignación de artículos a contenedores. Una solución factible es una solución en la que para cada contenedor el peso total de los artículos asignados es como máximo . La ganancia de la solución es la suma de las ganancias para cada asignación de artículo a contenedor. El objetivo es encontrar una solución factible de máxima ganancia. ${\displaystyle a_{1}}$ ${\displaystyle a_{n}}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{m}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle a_{j}}$ ${\displaystyle p_{ij}}$ ${\displaystyle w_{ij}}$ ${\displaystyle b_{i}}$ ${\displaystyle t_{i}}$

Matemáticamente, el problema de asignación generalizada se puede formular como un programa entero :

${\displaystyle {\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}}$

Complejidad

El problema de asignación generalizada es NP-duro . ^[1] Sin embargo, existen relajaciones de programación lineal que dan una aproximación. ^[2] ${\displaystyle (1-1/e)}$

Algoritmo de aproximación codiciosa

Para la variante del problema en la que no todos los elementos deben asignarse a un contenedor, existe una familia de algoritmos para resolver el GAP utilizando una traducción combinatoria de cualquier algoritmo para el problema de la mochila en un algoritmo de aproximación para el GAP. ^[3]

Utilizando cualquier algoritmo de aproximación ALG para el problema de la mochila , es posible construir una aproximación ( ) para el problema de asignación generalizada de una manera codiciosa utilizando un concepto de beneficio residual. El algoritmo construye un programa en iteraciones, donde durante la iteración se selecciona una selección tentativa de artículos para bin . La selección para bin puede cambiar a medida que los artículos pueden volver a seleccionarse en una iteración posterior para otros bins. El beneficio residual de un artículo para bin es si no se selecciona para ningún otro bin o – si se selecciona para bin . ${\displaystyle \alpha }$ ${\displaystyle \alpha +1}$ ${\displaystyle j}$ ${\displaystyle b_{j}}$ ${\displaystyle b_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{j}}$ ${\displaystyle p_{ij}}$ ${\displaystyle x_{i}}$ ${\displaystyle p_{ij}}$ ${\displaystyle p_{ik}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{k}}$

Formalmente: utilizamos un vector para indicar el cronograma tentativo durante el algoritmo. Específicamente, significa que el artículo está programado en el contenedor y significa que el artículo no está programado. La ganancia residual en la iteración se denota por , donde si el artículo no está programado (es decir, ) y si el artículo está programado en el contenedor (es decir, ). ${\displaystyle T}$ ${\displaystyle T[i]=j}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{j}}$ ${\displaystyle T[i]=-1}$ ${\displaystyle x_{i}}$ ${\displaystyle j}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{j}[i]=p_{ij}}$ ${\displaystyle x_{i}}$ ${\displaystyle T[i]=-1}$ ${\displaystyle P_{j}[i]=p_{ij}-p_{ik}}$ ${\displaystyle x_{i}}$ ${\displaystyle b_{k}}$ ${\displaystyle T[i]=k}$

Formalmente:

Colocar ${\displaystyle T[i]=-1{\text{ for }}i=1\ldots n}$

Para hacer: ${\displaystyle j=1,\ldots ,m}$

Llame a ALG para encontrar una solución para bin utilizando la función de beneficio residual . Denote los elementos seleccionados por . ${\displaystyle b_{j}}$ ${\displaystyle P_{j}}$ ${\displaystyle S_{j}}$

Actualizar usando , es decir, para todos . ${\displaystyle T}$ ${\displaystyle S_{j}}$ ${\displaystyle T[i]=j}$ ${\displaystyle i\in S_{j}}$

Véase también

• Problema de asignación

Referencias

1. Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Algoritmo de Bees para problemas de asignación generalizados , Applied Mathematics and Computation, vol. 215, Elsevier, págs. 3782–3795, doi :10.1016/j.amc.2009.11.018.
2. Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). Algoritmos de aproximación estricta para problemas de asignación general máxima . Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06. págs. 611–620.
3. Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "Una aproximación eficiente para el problema de asignación generalizada". Information Processing Letters . 100 (4): 162–166. CiteSeerX 10.1.1.159.1947 . doi :10.1016/j.ipl.2006.06.003. 

Lectura adicional

• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (19 de marzo de 2013). Problemas con la mochila . Saltador. ISBN 978-3-540-24777-7.