Lista de problemas de la mochila

El problema de la mochila es uno de los problemas más estudiados en optimización combinatoria , con muchas aplicaciones en la vida real. Por esta razón, se han examinado muchos casos especiales y generalizaciones. ^{[1] [2]}

Todas las versiones tienen en común un conjunto de n elementos, cada uno de los cuales tiene un beneficio asociado p _j y un peso w _j . La variable de decisión binaria x _j se utiliza para seleccionar el elemento. El objetivo es elegir algunos de los elementos con el máximo beneficio total, respetando que el peso total máximo de los elementos elegidos no debe superar W . Por lo general, estos coeficientes se escalan para convertirse en números enteros y casi siempre se supone que son positivos. ${\displaystyle 1\leq j\leq n}$

El problema de la mochila en su forma más básica:

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 entero positivo o infinito) sobre la cantidad de veces que se puede seleccionar el elemento j :

El problema de la mochila sin límites (a veces llamado el problema de la mochila entera ) no impone ningún límite superior al número de veces que se puede seleccionar un elemento:

Lueker demostró en 1975 que la variante ilimitada era NP-completa . ^[3] Tanto la variante ilimitada como la limitada 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 denominadas , y se debe tomar exactamente un elemento de cada clase, obtenemos el problema de la mochila de opción múltiple : ${\displaystyle N_{i}}$

Si para cada artículo la ganancia y el peso son iguales, obtenemos el problema de suma de subconjuntos (a menudo se da en su lugar el problema de decisión correspondiente):

Si tenemos n artículos y m mochilas con capacidades , obtenemos el problema de las mochilas múltiples : ${\displaystyle W_{i}}$

Como caso especial del problema de mochilas múltiples, 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 mochila cuadrático :

Problema de la mochila Set-Union :

^{Kellerer et al [2]} (en la página 423) definen SUKP de la siguiente manera:

Dado un conjunto de elementos y un conjunto de los denominados , cada elemento corresponde a un subconjunto del conjunto de elementos . Los elementos tienen beneficios no negativos , y los elementos tienen pesos no negativos , . El peso total de un conjunto de elementos está 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 los elementos con un peso total que no exceda la capacidad de la mochila y un beneficio máximo. ${\displaystyle n}$${\displaystyle N=\{1,\ldots ,n\}}$${\displaystyle m}$${\displaystyle P=\{1,\ldots ,m\}}$${\displaystyle j}$${\displaystyle P_{j}}$${\displaystyle P}$${\displaystyle j}$${\displaystyle p_{j}}$${\displaystyle j=1,\ldots ,n}$${\displaystyle i}$${\displaystyle w_{i}}$${\displaystyle i=1,\ldots ,m}$

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 elemento no están relacionados), obtenemos el problema de la mochila con restricciones múltiples , el problema de la mochila multidimensional o el problema de la mochila de m dimensiones . ( Nota: "dimensión" aquí no se refiere a la forma de ningún elemento). Esto tiene variantes 0-1, acotadas y no acotadas; la no acotada se muestra a continuación.

Se demostró que la variante 0-1 (para cualquier fijo ) es NP-completa alrededor de 1980 y, más firmemente, no tiene FPTAS a menos que P = NP. ^{[4] [5]}${\displaystyle m\geq 2}$

Las variantes acotadas y no acotadas (para cualquier ) fija también presentan la misma dureza. ^[6]${\displaystyle m\geq 2}$

Para cualquier fijo , estos problemas admiten un algoritmo de tiempo pseudopolinomial (similar al de la mochila básica) y un PTAS . ^[2]${\displaystyle m\geq 2}$

Si todas las ganancias son 1, intentaremos maximizar el número de artículos que no excedan la capacidad de la mochila:

Si tenemos varios contenedores (del mismo tamaño) y deseamos empaquetar todos los n artículos en la menor cantidad de contenedores posible, obtenemos el problema de empaquetado en contenedores , que se modela al tener como variables indicadoras el contenedor i en uso: ${\displaystyle y_{i}=1\Leftrightarrow }$

El problema del recorte de existencias es idéntico al problema del empaquetado en contenedores , pero como los casos prácticos suelen tener muchos menos tipos de artículos, a menudo se utiliza otra formulación. El artículo j se necesita B _j veces, cada "patrón" de artículos que caben en una sola mochila tiene una variable, x _i (hay m patrones), y el patrón i utiliza el artículo j b _ij veces:

Si al problema de la mochila de opción múltiple añadimos la restricción de que cada subconjunto es de tamaño n y eliminamos la restricción del peso total, obtenemos el problema de asignación , que es también el problema de encontrar una correspondencia bipartita máxima :

En la variante de mochila de máxima densidad hay un peso inicial y maximizamos la densidad de los elementos seleccionados que no violan la restricción de capacidad: ^[7]${\displaystyle w_{0}}$

Aunque son menos comunes que los anteriores, existen otros problemas similares a los de la mochila, entre ellos:

• Problema de la mochila anidada
• Problema de la mochila que se pliega
• Problema de la mochila no lineal
• Problema de la mochila paramétrico inverso

Los últimos tres de estos se analizan en la obra de referencia de Kellerer et al., Knapsack Problems . ^[2]

• "Algoritmos para problemas de mochila", D. Pisinger. Tesis doctoral, DIKU, Universidad de Copenhague, Informe 95/1 (1995).