Lista de problemas de mochila

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

Todas las versiones comparten un conjunto de n elementos, donde cada elemento${\displaystyle 1\leq j\leq n}$Cada elemento tiene una ganancia asociada 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 que maximicen la ganancia total, respetando que el peso total máximo de los elementos seleccionados no supere W. Generalmente, estos coeficientes se escalan para convertirse en números enteros y casi siempre se asume que son positivos.

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 el número de veces que se puede seleccionar el elemento j :

El problema de la mochila sin límite (a veces llamado 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 no acotada era NP-completa . ^{[ 3 ]} Tanto la variante acotada como la no acotada 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 denotadas${\displaystyle N_{i}}$y se debe tomar exactamente un artículo de cada clase, obtenemos el problema de la mochila de opción múltiple :

Si para cada artículo la ganancia y el peso son iguales, obtenemos el problema de la 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${\displaystyle W_{i}}$, obtenemos el problema de la mochila múltiple :

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 :

Problema de la mochila con unión de conjuntos :

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

Dado un conjunto de${\displaystyle n}$elementos${\displaystyle N=\{1,\ldots ,n\}}$y un conjunto de${\displaystyle m}$los llamados elementos${\displaystyle P=\{1,\ldots ,m\}}$, cada artículo${\displaystyle j}$corresponde a un subconjunto${\displaystyle P_{j}}$del conjunto de elementos${\displaystyle P}$Los artículos${\displaystyle j}$obtener beneficios no negativos${\displaystyle p_{j}}$,${\displaystyle j=1,\ldots ,n}$y los elementos${\displaystyle i}$tienen pesos no negativos${\displaystyle w_{i}}$,${\displaystyle i=1,\ldots ,m}$El peso total de un conjunto de artículos viene dado por la suma de los pesos de los elementos de la unión de los conjuntos de elementos correspondientes. El objetivo es encontrar un subconjunto de artículos cuyo peso total no supere la capacidad de la mochila y que genere el máximo beneficio.

Si existe 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 múltiples restricciones , el problema de la mochila multidimensional o el problema de la mochila m - dimensional . (Cabe destacar que "dimensión" aquí no se refiere a la forma de ningún artículo). Este problema tiene variantes binarias, acotadas e ilimitadas; la versión ilimitada se muestra a continuación.

La variante 0-1 (para cualquier fijo)${\displaystyle m\geq 2}$) 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 acotadas y no acotadas (para cualquier fijo)${\displaystyle m\geq 2}$) también exhiben la misma dureza. ^{[ 6 ]}

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

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

Si tenemos varios contenedores (del mismo tamaño) y deseamos empaquetar los n artículos en la menor cantidad de contenedores posible, obtenemos el problema de empaquetamiento de contenedores , que se modela mediante variables indicadoras.${\displaystyle y_{i}=1\Leftrightarrow}$El contenedor i está siendo utilizado:

El problema del corte de material es idéntico al problema del empaquetado de contenedores , pero dado que las instancias prácticas 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 le añadimos la restricción de que cada subconjunto tenga un 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 un emparejamiento bipartito maximal :

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

Aunque 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 desmorona
• Problema de la mochila no lineal
• Problema de la mochila paramétrico inverso

Los tres últimos se analizan en la obra de referencia de Kellerer et al., Problemas de la mochila . ^{[ 2 ]}

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