El problema de la mochila es uno de los problemas más estudiados en la optimización combinatoria , con muchas aplicaciones de la vida real. Por esta razón, se han examinado muchos casos especiales y generalizaciones. [1] [2]
Común a todas las versiones hay un conjunto de n elementos, con cada elementoteniendo una ganancia asociada p j , peso w j . La variable de decisión binaria x j se utiliza para seleccionar el elemento. El objetivo es escoger algunos de los artículos, con un beneficio máximo total, mientras que la obediencia que el peso total máximo de los elementos seleccionados no debe superar W . Generalmente, estos coeficientes se escalan para convertirse en números enteros y casi siempre se supone que son positivos.
El problema de la mochila en su forma más básica:
maximizar | ||
sujeto a | ||
Generalizaciones directas
Una variante común es que cada elemento se puede elegir varias veces. El problema de la mochila acotada especifica, para cada elemento j , un límite superior u j (que puede ser un número entero positivo o infinito) en el número de veces que se puede seleccionar el elemento j :
maximizar | ||
sujeto a | ||
integral para todo j |
El problema de la mochila ilimitada (a veces llamado el problema de la mochila entera ) no pone límites superiores al número de veces que se puede seleccionar un artículo:
maximizar | ||
sujeto a | ||
integral para todo j |
Lueker demostró que la variante ilimitada era NP-completa en 1975. [3] Tanto la variante limitada como la ilimitada admiten un FPTAS (esencialmente el mismo que el utilizado en el problema de la mochila 0-1).
Si los elementos se subdividen en k clases indicadas, y se debe tomar exactamente un elemento de cada clase, obtenemos el problema de la mochila de opción múltiple :
maximizar | ||
sujeto a | ||
para todos | ||
para todos y todo |
Si para cada artículo la ganancia y el peso son iguales, obtenemos el problema de la suma del subconjunto (a menudo se da el problema de decisión correspondiente en su lugar):
maximizar | ||
sujeto a | ||
Si tenemos n artículos y m mochilas con capacidades, obtenemos el problema de la mochila múltiple :
maximizar | ||
sujeto a | para todos | |
para todos | ||
para todos y todo |
Como caso especial del problema de la mochila múltiple, cuando las ganancias son iguales a los pesos y todos los contenedores tienen la misma capacidad, podemos tener un problema de suma de subconjuntos múltiples .
Problema de la mochila cuadrática :
maximizar | |||
sujeto a | |||
para todos |
Problema de la mochila de unión fijada :
Kellerer et al [2] (en la página 423) definen SUKP de la siguiente manera:
Dado un conjunto de artículos y un conjunto de los llamados elementos , cada elemento corresponde a un subconjunto del conjunto de elementos . Los artículos tener beneficios no negativos , , y los elementos tienen pesos no negativos , . El peso total de un conjunto de elementos viene dado por el peso total de los elementos de la unión de los conjuntos de elementos correspondientes. El objetivo es encontrar un subconjunto de artículos con un peso total que no exceda la capacidad de la mochila y el beneficio máximo.
Varias restricciones
Si hay más de una restricción (por ejemplo, un límite de volumen y un límite de peso, donde el volumen y el peso de cada artículo no están relacionados), obtenemos el problema de la mochila con restricciones múltiples , el problema de la mochila multidimensional o m - dimensional problema de la mochila . (Tenga en cuenta que aquí "dimensión" no se refiere a la forma de ningún elemento). Tiene variantes de 0 a 1, delimitadas y no delimitadas; el ilimitado se muestra a continuación.
maximizar | ||
sujeto a | para todos | |
, entero | para todos |
La variante 0-1 (para cualquier fijo ) se demostró que era NP-completo alrededor de 1980 y, más fuertemente, no tiene FPTAS a menos que P = NP. [4] [5]
Las variantes limitadas y no limitadas (para cualquier fijo ) también presentan la misma dureza. [6]
Para cualquier fijo , estos problemas admiten un algoritmo de tiempo pseudopolinomial (similar al de la mochila básica) y un PTAS . [2]
Problemas de mochila
Si todas las ganancias son 1, intentaremos maximizar la cantidad de artículos que no excedan la capacidad de la mochila:
maximizar | ||
sujeto a | ||
Si tenemos varios contenedores (del mismo tamaño), y deseamos empacar todos los n artículos en el menor número posible de contenedores, obtenemos el problema de empaquetado en contenedores , que se modela con variables indicadorascontenedor i se está utilizando:
minimizar | ||
sujeto a | ||
El problema del material de corte es idéntico al problema del embalaje en contenedores , pero dado que los casos prácticos suelen tener muchos menos tipos de artículos, a menudo se utiliza otra formulación. El elemento j se necesita B j veces, cada "patrón" de elementos que caben en una sola mochila tiene una variable, x i (hay m patrones), y el patrón i usa el elemento j b ij veces:
minimizar | ||
sujeto a | para todos | |
para todos |
Si, al problema de la mochila de opción múltiple, agregamos la restricción de que cada subconjunto es de tamaño n y eliminamos la restricción sobre el peso total, obtenemos el problema de asignación , que también es el problema de encontrar una coincidencia máxima bipartita :
maximizar | ||
sujeto a | para todos | |
para todos | ||
para todos y todo |
En la variante Mochila de máxima densidad hay un peso inicial, y maximizamos la densidad de elementos seleccionados que no violan la restricción de capacidad: [7]
maximizar | ||
sujeto a | ||
Aunque son menos comunes que los anteriores, existen varios otros problemas similares a los de una mochila, que incluyen:
- Problema de mochila anidada
- Problema de mochila colapsada
- Problema de mochila no lineal
- Problema de mochila paramétrico inverso
Los últimos tres de estos se analizan en el trabajo de referencia de Kellerer et al, Problemas de mochila . [2]
Referencias
- ^ Martello, Silvano y Toth, Paolo (1990). Problemas de mochila: algoritmos e implementaciones informáticas . John Wiley e hijos . ISBN 978-0471924203.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ a b c d Kellerer, Hans y Pferschy, Ulrich y Pisinger, David (2004). Problemas con la mochila . Springer Verlag . ISBN 978-3-540-40286-2.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Lueker, GS (1975). "Dos problemas NP-completos en programación de enteros no negativos". Informe No. 178, Laboratorio de Ciencias de la Computación, Princeton. Cite journal requiere
|journal=
( ayuda ) - ^ Gens, GV y Levner, EV (1979). "Algoritmos de complejidad y aproximación para problemas combinatorios: una encuesta". Instituto Central de Economía y Matemáticas, Academia de Ciencias de la URSS, Moscú.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ "Sobre la existencia de esquemas de aproximación rápida". Programación no lineal . 4 : 415–437. 1980.
- ^ Revista, MJ; Chern, M.-S. (1984). "Una nota sobre esquemas de aproximación para problemas multidimensionales de mochila". Matemáticas de la investigación operativa . 9 (2): 244–247. doi : 10.1287 / moor.9.2.244 .
- ^ Cohen, Reuven; Katzir, Liran (2008). "El problema de la cobertura máxima generalizada". Cartas de procesamiento de información . 108 : 15-22. CiteSeerX 10.1.1.156.2073 . doi : 10.1016 / j.ipl.2008.03.017 .
- "Algoritmos para problemas de mochila" , D. Pisinger. Doctor. tesis, DIKU, Universidad de Copenhague, Informe 95/1 (1995).