Problema de mochila

Problema en la optimización combinatoria

Ejemplo de un problema de mochila unidimensional (restricción): ¿qué cajas se deben elegir para maximizar la cantidad de dinero mientras se mantiene el peso total por debajo o igual a 15 kg? Un problema de restricciones múltiples podría considerar tanto el peso como el volumen de las cajas.
(Solución: si cualquier número de cada casilla está disponible, entonces tres casillas amarillas y tres casillas grises; si solo están disponibles las casillas que se muestran, entonces todas, pero no la casilla verde).

El problema de la mochila es un problema de optimización combinatoria : dado un conjunto de artículos, cada uno con un peso y un valor, determine el número de cada artículo para incluir en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total es lo más grande posible. Deriva su nombre del problema que enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarla con los artículos más valiosos. El problema a menudo surge en la asignación de recursos, donde los tomadores de decisiones tienen que elegir entre un conjunto de proyectos o tareas no divisibles con un presupuesto fijo o una restricción de tiempo, respectivamente.

El problema de la mochila se ha estudiado durante más de un siglo, y los primeros trabajos datan de 1897. ^[1] El nombre "problema de la mochila" se remonta a los primeros trabajos del matemático Tobias Dantzig (1884-1956), ^{[2 ]} y se refiere al problema común de empacar los artículos más valiosos o útiles sin sobrecargar el equipaje.

Aplicaciones

Los problemas de la mochila aparecen en los procesos de toma de decisiones del mundo real en una amplia variedad de campos, como encontrar la forma menos derrochadora de cortar materias primas, ^[3] selección de inversiones y carteras , ^[4] selección de activos para titulización respaldada por activos. , ^[5] y generación de claves para Merkle-Hellman ^[6] y otros criptosistemas de mochila .

Una de las primeras aplicaciones de los algoritmos de la mochila fue en la construcción y puntuación de pruebas en las que los examinados pueden elegir a qué preguntas responder. Para pequeños ejemplos, es un proceso bastante simple proporcionar a los examinados esa opción. Por ejemplo, si un examen contiene 12 preguntas, cada una con un valor de 10 puntos, el examinado solo necesita responder 10 preguntas para lograr una puntuación máxima posible de 100 puntos. Sin embargo, en las pruebas con una distribución heterogénea de valores de puntos, es más difícil proporcionar opciones. Feuerman y Weiss propusieron un sistema en el que a los estudiantes se les da una prueba heterogénea con un total de 125 puntos posibles. Se pide a los estudiantes que respondan todas las preguntas lo mejor que puedan. De los posibles subconjuntos de problemas cuyos valores totales de puntos suman 100,un algoritmo de mochila determinaría qué subconjunto da a cada estudiante la puntuación más alta posible.^[7]

Un estudio de 1999 del Repositorio de Algoritmos de la Universidad de Stony Brook mostró que, de 75 problemas algorítmicos, el problema de la mochila era el decimonoveno más popular y el tercero más necesario después de los árboles de sufijos y el problema del embalaje de contenedores . ^[8]

Definición

El problema más común que se resuelve es el problema de la mochila 0-1 , que restringe el número de copias de cada tipo de artículo a cero o uno. Dado un conjunto de artículos numerados del 1 al , cada uno con un peso y un valor , junto con una capacidad máxima de peso ,${\displaystyle x_{i}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle w_{i}}$${\displaystyle v_{i}}$${\displaystyle W}$

maximizar ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a y .${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$${\displaystyle x_{i}\in \{0,1\}}$

Aquí representa el número de instancias de artículo para incluir en la mochila. De manera informal, el problema es maximizar la suma de los valores de los artículos en la mochila de modo que la suma de los pesos sea menor o igual a la capacidad de la mochila.${\displaystyle x_{i}}$${\displaystyle i}$

El problema de la mochila acotada ( BKP ) elimina la restricción de que solo hay uno de cada artículo, pero restringe el número de copias de cada tipo de artículo a un valor entero no negativo máximo :${\displaystyle x_{i}}$${\displaystyle c}$

maximizar ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a y${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$${\displaystyle x_{i}\in \{0,1,2,\dots ,c\}.}$

El problema de la mochila ilimitada ( UKP ) no establece un límite superior en el número de copias de cada tipo de artículo y se puede formular como se indicó anteriormente, excepto que la única restricción es que es un número entero no negativo.${\displaystyle x_{i}}$

maximizar ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a y${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$${\displaystyle x_{i}\geq 0,\ x_{i}\in \mathbb {Z} .}$

Se da un ejemplo del problema ilimitado de la mochila usando la figura que se muestra al principio de este artículo y el texto "si hay algún número de cada caja disponible" en el título de esa figura.

Complejidad computacional

El problema de la mochila es interesante desde la perspectiva de la informática por muchas razones:

• La forma del problema de decisión del problema de la mochila ( ¿Se puede lograr un valor de al menos V sin exceder el peso W ? ) Es NP-completo , por lo que no existe un algoritmo conocido tanto correcto como rápido (polinomio-tiempo) en todos los casos.
• Si bien el problema de decisión es NP-completo, el problema de optimización no lo es, su resolución es al menos tan difícil como el problema de decisión, y no existe un algoritmo polinomial conocido que pueda decir, dada una solución, si es óptima (lo que significaría que no hay solución con una V mayor , resolviendo así el problema de decisión NP-completo).
• Existe un algoritmo de tiempo pseudopolinomial que utiliza programación dinámica .
• Existe un esquema de aproximación de tiempo completamente polinomial , que utiliza el algoritmo de tiempo pseudopolinomial como una subrutina, que se describe a continuación.
• No obstante, muchos casos que surgen en la práctica y "instancias aleatorias" de algunas distribuciones pueden resolverse con exactitud.

Existe un vínculo entre los problemas de "decisión" y "optimización" en el sentido de que si existe un algoritmo polinomial que resuelve el problema de "decisión", entonces se puede encontrar el valor máximo para el problema de optimización en tiempo polinomial aplicando este algoritmo iterativamente mientras aumentando el valor de k. Por otro lado, si un algoritmo encuentra el valor óptimo del problema de optimización en tiempo polinomial, entonces el problema de decisión se puede resolver en tiempo polinomial comparando el valor de la salida de solución de este algoritmo con el valor de k. Por tanto, ambas versiones del problema presentan una dificultad similar.

Un tema en la literatura de investigación es identificar cómo se ven los casos "difíciles" del problema de la mochila, ^{[9] [10]} o visto de otra manera, para identificar qué propiedades de los casos en la práctica podrían hacerlos más fáciles de manejar que en el peor de los casos. Sugiere un comportamiento NP-completo. ^[11] El objetivo de encontrar estas instancias "difíciles" es su uso en sistemas de criptografía de clave pública , como el criptosistema de mochila Merkle-Hellman .

Además, es notable el hecho de que la dureza del problema de la mochila depende de la forma de la entrada. Si los pesos y las ganancias se dan como números enteros, es débilmente NP-completo , mientras que es fuertemente NP-completo si los pesos y las ganancias se dan como números racionales. ^[12] Sin embargo, en el caso de pesos y ganancias racionales, todavía admite un esquema de aproximación de tiempo completamente polinomial .

Resolviendo

Hay varios algoritmos disponibles para resolver problemas de mochila, basados ​​en el enfoque de programación dinámica, ^[13] el enfoque de ramificación y límite ^[14] o hibridaciones de ambos enfoques. ^{[11] [15] [16] [17]}

Algoritmo avanzado de programación dinámica

El problema de la mochila ilimitada ( UKP ) no impone restricciones al número de copias de cada tipo de artículo. Además, aquí asumimos que${\displaystyle x_{i}>0}$

${\displaystyle m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)}$

sujeto a y${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq w'}$${\displaystyle x_{i}>0}$

Observe que tiene las siguientes propiedades:${\displaystyle m[w]}$

1. (la suma de cero elementos, es decir, la suma del conjunto vacío).${\displaystyle m[0]=0\,\!}$

2 . ,, donde es el valor del -ésimo tipo de artículo.${\displaystyle m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])}$${\displaystyle w_{i}\leq w}$${\displaystyle v_{i}}$${\displaystyle i}$

La segunda propiedad debe explicarse en detalle. Durante el proceso de ejecución de este método, ¿cómo obtenemos el peso ? Solo hay formas y los pesos anteriores son donde hay tipos totales de elementos diferentes (al decir diferentes, queremos decir que el peso y el valor no son completamente iguales). Si conocemos previamente cada valor de estos elementos y el valor máximo relacionado, simplemente los comparamos entre sí y obtenemos el valor máximo en última instancia y listo.${\displaystyle w}$${\displaystyle i}$${\displaystyle w-w_{1},w-w_{2},...,w-w_{i}}$${\displaystyle i}$${\displaystyle i}$

Aquí, el máximo del conjunto vacío se toma como cero. Tabular los resultados desde arriba da la solución. Dado que el cálculo de cada uno implica examinar como máximo los elementos, y hay como máximo valores de para calcular, el tiempo de ejecución de la solución de programación dinámica es . Dividir por su máximo común divisor es una forma de mejorar el tiempo de ejecución.${\displaystyle m[0]}$${\displaystyle m[W]}$${\displaystyle m[w]}$${\displaystyle n}$${\displaystyle W}$${\displaystyle m[w]}$ O ( n W ) {\displaystyle O(nW)} ${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$

Incluso si P ≠ NP , la complejidad no contradice el hecho de que el problema de la mochila es NP-completo , ya que , a diferencia , no es polinomial en la longitud de la entrada al problema. La longitud de la entrada al problema es proporcional al número de bits en , , no para sí mismo. Sin embargo, dado que este tiempo de ejecución es pseudopolinomial , esto hace que la (versión de decisión del) problema de la mochila sea un problema débilmente NP-completo .${\displaystyle O(nW)}$${\displaystyle W}$${\displaystyle n}$${\displaystyle W}$${\displaystyle W}$${\displaystyle \log W}$${\displaystyle W}$

0-1 problema de mochila

Una solución de programación dinámica similar para el problema de la mochila 0-1 también se ejecuta en tiempo pseudopolinomial. Supongamos que son enteros estrictamente positivos. Defínalo como el valor máximo que se puede alcanzar con un peso menor o igual que el uso de elementos hasta (primeros elementos).${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$${\displaystyle m[i,w]}$${\displaystyle w}$${\displaystyle i}$${\displaystyle i}$

Podemos definir de forma recursiva como sigue: (Definición A)${\displaystyle m[i,w]}$

• ${\displaystyle m[0,\,w]=0}$
• ${\displaystyle m[i,\,w]=m[i-1,\,w]}$si (el nuevo artículo supera el límite de peso actual)${\displaystyle w_{i}>w\,\!}$
• ${\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}$si .${\displaystyle w_{i}\leqslant w}$

La solución se puede encontrar calculando . Para hacer esto de manera eficiente, podemos usar una tabla para almacenar cálculos anteriores.${\displaystyle m[n,W]}$

El siguiente es un pseudocódigo para el programa dinámico:

// Aporte:// Valores (almacenados en matriz v)// Pesos (almacenados en la matriz w)// Número de elementos distintos (n)// Capacidad de la mochila (W)// NOTA: Se supone que la matriz "v" y la matriz "w" almacenan todos los valores relevantes a partir del índice 1.matriz  m [ 0 .. n ,  0 .. W ];para  j  de  0  a  W  hacer : m [ 0 ,  j ]  : =  0para  i  de  1  a  n  hago : m [ i ,  0 ]  : =  0para  i  de  1  a  n  hago : para  j  de  0  a  W  hacer : si  w [ i ]  >  j  entonces : m [ i ,  j ]  : =  m [ i -1 ,  j ] otra cosa : m [ i ,  j ]  : =  max ( m [ i -1 ,  j ],  m [ i -1 ,  j - w [ i ]]  +  v [ i ])

Por tanto, esta solución se ejecutará en el tiempo y el espacio. (Si solo necesitamos el valor m [n, W], podemos modificar el código para que la cantidad de memoria requerida sea O (W) que almacena las dos líneas recientes de la matriz "m").${\displaystyle O(nW)}$${\displaystyle O(nW)}$

Sin embargo, si damos un paso o dos más, debemos saber que el método se ejecutará en el tiempo entre y . De la definición A , podemos saber que no hay necesidad de calcular todos los pesos cuando el número de elementos y los elementos mismos que elegimos son fijos. Es decir, el programa anterior calcula más de lo necesario porque el peso cambia de 0 a W todo el tiempo. Desde esta perspectiva, podemos programar este método para que se ejecute de forma recursiva.${\displaystyle O(nW)}$${\displaystyle O(2^{n})}$

// Aporte:// Valores (almacenados en matriz v)// Pesos (almacenados en la matriz w)// Número de elementos distintos (n)// Capacidad de la mochila (W)// NOTA: Se supone que la matriz "v" y la matriz "w" almacenan todos los valores relevantes a partir del índice 1.Definir  valor [ n ,  W ]Inicializar  todo el  valor [ i ,  j ]  =  -1Definir  m : = ( i , j )  // Definir la función m para que represente el valor máximo que podemos obtener bajo la condición: use primero i elementos, el límite de peso total es j{ si  i  ==  0  o  j  <=  0  entonces : valor [ i ,  j ]  =  0 regreso si  ( valor [ i -1 ,  j ]  ==  -1 )  entonces :  // m [i-1, j] no se ha calculado, tenemos que llamar a la función m valor [ i -1 ,  j ]  =  m ( i -1 ,  j ) si  w [ i ]  >  j  entonces :  // el artículo no cabe en la bolsa valor [ i ,  j ]  =  valor [ i -1 ,  j ] otra cosa :  si  ( valor [ i -1 ,  j - w [ i ]]  ==  -1 )  entonces :  // m [i-1, jw [i]] no se ha calculado, tenemos que llamar a la función m valor [ i -1 ,  j - w [ i ]]  =  m ( i -1 ,  j - w [ i ]) valor [ i ,  j ]  =  max ( valor [ i -1 , j ],  valor [ i -1 ,  j - w [ i ]]  +  v [ i ])}Ejecutar  m ( n ,  W )

Por ejemplo, hay 10 artículos diferentes y el límite de peso es 67. Entonces,

${\displaystyle {\begin{aligned}&w[1]=23,w[2]=26,w[3]=20,w[4]=18,w[5]=32,w[6]=27,w[7]=29,w[8]=26,w[9]=30,w[10]=27\\&v[1]=505,v[2]=352,v[3]=458,v[4]=220,v[5]=354,v[6]=414,v[7]=498,v[8]=545,v[9]=473,v[10]=543\\\end{aligned}}}$

Si usa el método anterior para calcular , obtendrá esto, excluyendo las llamadas que producen :${\displaystyle m(10,67)}$${\displaystyle m(i,j)=0}$

${\displaystyle {\begin{aligned}&m(10,67)=1270\\&m(9,67)=1270,m(9,40)=678\\&m(8,67)=1270,m(8,40)=678,m(8,37)=545\\&m(7,67)=1183,m(7,41)=725,m(7,40)=678,m(7,37)=505\\&m(6,67)=1183,m(6,41)=725,m(6,40)=678,m(6,38)=678,m(6,37)=505\\&m(5,67)=1183,m(5,41)=725,m(5,40)=678,m(5,38)=678,m(5,37)=505\\&m(4,67)=1183,m(4,41)=725,m(4,40)=678,m(4,38)=678,m(4,37)=505,m(4,35)=505\\&m(3,67)=963,m(3,49)=963,m(3,41)=505,m(3,40)=505,m(3,38)=505,m(3,37)=505,m(3,35)=505,m(3,23)=505,m(3,22)=458,m(3,20)=458\\&m(2,67)=857,m(2,49)=857,m(2,47)=505,m(2,41)=505,m(2,40)=505,m(2,38)=505,m(2,37)=505,m(2,35)=505,m(2,29)=505,m(2,23)=505\\&m(1,67)=505,m(1,49)=505,m(1,47)=505,m(1,41)=505,m(1,40)=505,m(1,38)=505,m(1,37)=505,m(1,35)=505,m(1,29)=505,m(1,23)=505\\\end{aligned}}}$

Además, podemos romper la recursividad y convertirla en un árbol. Luego, podemos cortar algunas hojas y usar la computación paralela para acelerar la ejecución de este método.

Para encontrar el subconjunto real de elementos, en lugar de solo su valor total, podemos ejecutar esto después de ejecutar la función anterior:

/ ** * Devuelve los índices de los elementos de la mochila óptima. * i: podemos incluir los elementos 1 a i en la mochila * j: peso máximo de la mochila * /función  mochila ( i :  int ,  j :  int ) :  Set < int >  { si  i  ==  0  entonces : volver  {} si  m [ i ,  j ]  >  m [ i -1 ,  j ]  entonces : devolver  { i }  ∪  mochila ( i -1 ,  j - w [ i ]) otra cosa : devolver  mochila ( i -1 ,  j )}mochila ( n ,  W )

Meet-in-the-middle

Otro algoritmo para la mochila 0-1, descubierto en 1974 ^[18] y a veces llamado "encuentro en el medio" debido a los paralelos con un algoritmo de nombre similar en criptografía , es exponencial en el número de elementos diferentes, pero puede ser preferible a el algoritmo DP cuando es grande en comparación con n . En particular, si no son negativos pero no enteros, aún podríamos usar el algoritmo de programación dinámica escalando y redondeando (es decir, usando aritmética de punto fijo ), pero si el problema requiere dígitos fraccionarios de precisión para llegar a la respuesta correcta, necesitará escalar , y el algoritmo DP requerirá espacio y tiempo.${\displaystyle W}$${\displaystyle w_{i}}$${\displaystyle d}$${\displaystyle W}$${\displaystyle 10^{d}}$${\displaystyle O(W10^{d})}$${\displaystyle O(nW10^{d})}$

algoritmo Meet-en-el-medio es  de entrada: Un conjunto de elementos con pesos y valores. salida: el mayor valor combinado de un subconjunto. dividir el conjunto {1 ... n } en dos conjuntos A y B de aproximadamente el mismo tamaño calcular los pesos y valores de todos los subconjuntos de cada conjunto para cada subconjunto de  A  , encuentre el subconjunto de B de mayor valor tal que el peso combinado sea menor que W realizar un seguimiento del mayor valor combinado visto hasta ahora

El algoritmo ocupa espacio y las implementaciones eficientes del paso 3 (por ejemplo, clasifica los subconjuntos de B por peso, descarta los subconjuntos de B que pesan más que otros subconjuntos de B de mayor o igual valor y utiliza la búsqueda binaria para encontrar la mejor coincidencia ) dan como resultado un tiempo de ejecución de . Al igual que con el ataque de encuentro en el medio en criptografía, esto mejora el tiempo de ejecución de un enfoque de fuerza bruta ingenuo (examinando todos los subconjuntos de ), a costa de usar espacio exponencial en lugar de constante (ver también paso de bebé paso de gigante ).${\displaystyle O(2^{n/2})}$${\displaystyle O(n2^{n/2})}$${\displaystyle O(n2^{n})}$${\displaystyle \{1...n\}}$

Algoritmos de aproximación

Como para la mayoría de los problemas NP-completos, puede ser suficiente encontrar soluciones viables incluso si no son óptimas. Preferiblemente, sin embargo, la aproximación viene con una garantía de la diferencia entre el valor de la solución encontrada y el valor de la solución óptima.

Al igual que con muchos algoritmos útiles pero computacionalmente complejos, se han realizado investigaciones sustanciales sobre la creación y el análisis de algoritmos que se aproximen a una solución. El problema de la mochila, aunque NP-Hard, pertenece a una colección de algoritmos que aún se pueden aproximar a cualquier grado específico. Esto significa que el problema tiene un esquema de aproximación de tiempo polinomial. Para ser exactos, el problema de la mochila tiene un esquema de aproximación de tiempo completamente polinomial (FPTAS). ^[19]

Algoritmo de aproximación codicioso

George Dantzig propuso un algoritmo de aproximación codicioso para resolver el problema ilimitado de la mochila. ^[20] Su versión ordena los artículos en orden de valor por unidad de peso decreciente, . Luego procede a insertarlos en el saco, comenzando con tantas copias como sea posible del primer tipo de artículo hasta que ya no haya espacio en el saco para más. Siempre que haya un suministro ilimitado de cada tipo de artículo, si es el valor máximo de artículos que caben en el saco, entonces se garantiza que el algoritmo codicioso alcanzará al menos un valor de .${\displaystyle v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}}$${\displaystyle m}$${\displaystyle m/2}$

Para el problema delimitado, donde el suministro de cada tipo de artículo es limitado, el algoritmo anterior puede estar lejos de ser óptimo. Sin embargo, una simple modificación nos permite resolver este caso: construir una solución empacando los artículos con avidez el mayor tiempo posible, es decir, dónde . Además, construya una segunda solución que contenga el primer elemento que no encajaba. Dado que proporciona un límite superior para la relajación LP del problema, uno de los conjuntos debe tener valor al menos ; que de este modo devolver cualquiera de y tiene mejor valor para obtener una : Aproximación.${\displaystyle S_{1}}$${\displaystyle S_{1}=\left\{1,\ldots ,k\right\}}$${\displaystyle k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W}$${\displaystyle S_{2}=\left\{k+1\right\}}$${\displaystyle S_{1}\cup S_{2}}$${\displaystyle m/2}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle 1/2}$

Esquema de aproximación de tiempo completamente polinomial

El esquema de aproximación de tiempo completamente polinomial (FPTAS) para el problema de la mochila se aprovecha del hecho de que la razón por la que el problema no tiene soluciones de tiempo polinomiales conocidas es porque las ganancias asociadas con los artículos no están restringidas. Si se redondea algunos de los dígitos menos significativos de los valores de beneficio, entonces estarán delimitados por un polinomio y 1 / ε donde ε es un límite en la corrección de la solución. Esta restricción significa entonces que un algoritmo puede encontrar una solución en tiempo polinomial que sea correcta dentro de un factor de (1-ε) de la solución óptima. ^[19]

algoritmo FPTAS es  entrada: ε ∈ (0,1] una lista A de n elementos, especificados por sus valores , y la salida de ponderaciones : S 'la solución FPTAS${\displaystyle v_{i}}$ P: = max // el valor más alto del artículo${\displaystyle \{v_{i}\mid 1\leq i\leq n\}}$ K: = ε ${\displaystyle {\frac {P}{n}}}$ para i de 1 a n do  : = extremo para${\displaystyle v'_{i}}$${\displaystyle \left\lfloor {\frac {v_{i}}{K}}\right\rfloor }$  devolver la solución, S ', utilizando los valores del programa dinámico descrito anteriormente${\displaystyle v'_{i}}$

Teorema: El conjunto calculado por el algoritmo anterior satisface , donde es una solución óptima.${\displaystyle S'}$${\displaystyle \mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})}$${\displaystyle S^{*}}$

Relaciones de dominación

Resolver el problema ilimitado de la mochila puede ser más fácil desechando artículos que nunca serán necesarios. Para un artículo dado , suponga que podemos encontrar un conjunto de artículos tal que su peso total sea menor que el peso de y su valor total sea mayor que el valor de . Entonces no puede aparecer en la solución óptima, porque siempre podríamos mejorar cualquier solución potencial que contenga reemplazándola con el conjunto . Por lo tanto, podemos ignorar el -ésimo elemento por completo. En tales casos, se dice que domina . (Tenga en cuenta que esto no se aplica a los problemas de mochilas delimitadas, ya que es posible que ya hayamos agotado los elementos ).${\displaystyle i}$${\displaystyle J}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$${\displaystyle J}$${\displaystyle i}$${\displaystyle J}$ ${\displaystyle i}$${\displaystyle J}$

Encontrar relaciones de dominancia nos permite reducir significativamente el tamaño del espacio de búsqueda. Hay varios tipos diferentes de relaciones de dominancia , ^[11] que satisfacen todas una desigualdad de la forma:

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$y para algunos${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$${\displaystyle x\in Z_{+}^{n}}$

donde y . El vector denota el número de copias de cada miembro de .${\displaystyle \alpha \in Z_{+}\,,J\subsetneq N}$${\displaystyle i\not \in J}$${\displaystyle x}$${\displaystyle J}$

Dominio colectivo

El -ésimo elemento está dominado colectivamente por , escrito como , si el peso total de alguna combinación de elementos en es menor que w _i y su valor total es mayor que v _i . Formalmente, y para algunos , es decir . Verificar este dominio es computacionalmente difícil, por lo que solo se puede usar con un enfoque de programación dinámica. De hecho, esto es equivalente a resolver un problema de decisión mochila pequeña donde , y los artículos están restringidos a .${\displaystyle i}$${\displaystyle J}$${\displaystyle i\ll J}$${\displaystyle J}$${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}}$${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}}$${\displaystyle x\in Z_{+}^{n}}$${\displaystyle \alpha =1}$${\displaystyle V=v_{i}}$${\displaystyle W=w_{i}}$${\displaystyle J}$

Dominio de umbral

El -ésimo elemento es el umbral dominado por , escrito como , si cierto número de copias de están dominados por . Formalmente, y para algunos y . Esta es una generalización del dominio colectivo, introducida por primera vez en ^[13] y utilizada en el algoritmo EDUK. El más pequeño define el umbral del artículo , escrito . En este caso, la solución óptima podría contener como máximo copias de .${\displaystyle i}$${\displaystyle J}$${\displaystyle i\prec \prec J}$${\displaystyle i}$${\displaystyle J}$${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$${\displaystyle x\in Z_{+}^{n}}$${\displaystyle \alpha \geq 1}$${\displaystyle \alpha }$${\displaystyle i}$${\displaystyle t_{i}=(\alpha -1)w_{i}}$${\displaystyle \alpha -1}$${\displaystyle i}$

Dominio múltiple

El elemento -ésimo está dominado por un solo elemento , escrito como , si está dominado por un número de copias de . Formalmente, y para algunos, es decir . Esta dominancia podría usarse de manera eficiente durante el preprocesamiento porque se puede detectar con relativa facilidad.${\displaystyle i}$${\displaystyle j}$${\displaystyle i\ll _{m}j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle w_{j}\,x_{j}\ \leq w_{i}}$${\displaystyle v_{j}\,x_{j}\ \geq v_{i}}$${\displaystyle x_{j}\in Z_{+}}$${\displaystyle J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor }$

Dominio modular

Sea el mejor artículo , es decir, para todos . Este es el artículo con mayor densidad de valor. El -ésimo elemento está dominado modularmente por un solo elemento , escrito como , si está dominado por más varias copias de . Formalmente, y es decir .${\displaystyle b}$${\displaystyle {\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,}$${\displaystyle i}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i\ll _{\equiv }j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle b}$${\displaystyle w_{j}+tw_{b}\leq w_{i}}$${\displaystyle v_{j}+tv_{b}\geq v_{i}}$${\displaystyle J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1}$

Variaciones

Artículo principal: Lista de problemas con la mochila

Hay muchas variaciones del problema de la mochila que han surgido de la gran cantidad de aplicaciones del problema básico. Las principales variaciones se producen al cambiar el número de algún parámetro del problema como el número de elementos, el número de objetivos o incluso el número de mochilas.

Problema de mochila multiobjetivo

Esta variación cambia el objetivo del individuo que llena la mochila. En lugar de un objetivo, como maximizar la ganancia monetaria, el objetivo podría tener varias dimensiones. Por ejemplo, podría haber preocupaciones ambientales o sociales, además de objetivos económicos. Los problemas que se abordan con frecuencia incluyen optimizaciones de logística de transporte y cartera. ^{[21] [22]}

Por ejemplo, suponga que tiene un crucero. Tienes que decidir cuántos comediantes famosos contratar. Este barco no puede transportar más de una tonelada de pasajeros y los animadores deben pesar menos de 1000 libras. Cada comediante tiene un peso, genera negocios en función de su popularidad y pide un salario específico. En este ejemplo, tiene varios objetivos. Desea, por supuesto, maximizar la popularidad de sus artistas mientras minimiza sus salarios. Además, desea tener tantos animadores como sea posible.

Problema de mochila multidimensional

En esta variación, el peso de la mochila viene dado por un vector D-dimensional y la mochila tiene un vector de capacidad D-dimensional . El objetivo es maximizar la suma de los valores de los artículos en la mochila para que la suma de pesos en cada dimensión no exceda .${\displaystyle i}$${\displaystyle {\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})}$${\displaystyle (W_{1},\ldots ,W_{D})}$${\displaystyle d}$${\displaystyle W_{d}}$

La mochila multidimensional es computacionalmente más difícil que la mochila; incluso para , el problema no tiene EPTAS a menos que P NP. ^[23] Sin embargo, se muestra que el algoritmo en ^[24] resuelve instancias dispersas de manera eficiente. Una instancia de mochila multidimensional es escasa si hay un conjunto para tal que para cada artículo de mochila , tal que y . Tales casos ocurren, por ejemplo, al programar paquetes en una red inalámbrica con nodos de retransmisión. ^[24] El algoritmo de ^[24] también resuelve casos escasos de la variante de opción múltiple, la mochila multidimensional de opción múltiple.${\displaystyle D=2}$${\displaystyle =}$${\displaystyle J=\{1,2,\ldots ,m\}}$${\displaystyle m<D}$${\displaystyle i}$${\displaystyle \exists z>m}$${\displaystyle \forall j\in J\cup \{z\},\ w_{ij}\geq 0}$${\displaystyle \forall y\notin J\cup \{z\},w_{iy}=0}$

El algoritmo IHS (Increasing Height Shelf) es óptimo para la mochila 2D (empaquetar cuadrados en un cuadrado de tamaño de unidad bidimensional): cuando hay como máximo cinco cuadrados en un empaque óptimo. ^[25]

Problema con varias mochilas

Esta variación es similar al problema del embalaje del contenedor . Se diferencia del problema de embalaje en contenedores en que se puede seleccionar un subconjunto de artículos, mientras que, en el problema de embalaje en contenedores, todos los artículos deben empaquetarse en determinados contenedores. El concepto es que hay varias mochilas. Esto puede parecer un cambio trivial, pero no equivale a aumentar la capacidad de la mochila inicial. Esta variación se utiliza en muchos problemas de carga y programación en Investigación de operaciones y tiene un esquema de aproximación de tiempo polinómico . ^[26]

Problema cuadrático de la mochila

El problema de la mochila cuadrática maximiza una función objetivo cuadrática sujeta a restricciones de capacidad lineal y binaria. ^[27] El problema fue introducido por Gallo, Hammer y Simeone en 1980, ^[28] sin embargo, el primer tratamiento del problema se remonta a Witzgall en 1975. ^[29]

Problema de suma de subconjuntos

El problema de la suma de subconjuntos es un caso especial de la decisión y 0-1 problemas que cada tipo de artículo, el peso es igual al valor: . En el campo de la criptografía , el término problema de la mochila se usa a menudo para referirse específicamente al problema de la suma de subconjuntos y se conoce comúnmente como uno de los 21 problemas NP-completos de Karp . ^[30]${\displaystyle w_{i}=v_{i}}$

La generalización del problema de suma de subconjuntos se denomina problema de suma de subconjuntos múltiples, en el que existen varios contenedores con la misma capacidad. Se ha demostrado que la generalización no tiene FPTAS . ^[31]

Problema de mochila geométrica

En el problema de la mochila geométrica , hay un conjunto de rectángulos con diferentes valores y una mochila rectangular. El objetivo es empacar el mayor valor posible en la mochila. ^[32]

Ver también

• Problema de cambio
• Subasta combinatoria
• Optimización combinatoria
• Problema continuo de la mochila
• Problema de stock de corte
• Lista de problemas con la mochila
• Problema de embalaje

Notas

1. Mathews, GB (25 de junio de 1897). "Sobre la partición de números" (PDF) . Actas de la London Mathematical Society . 28 : 486–490. doi : 10.1112 / plms / s1-28.1.486 .
2. Dantzig, Tobías. Números: El lenguaje de la ciencia, 1930.
3. Kellerer, Pferschy y Pisinger 2004, p. 449
4. Kellerer, Pferschy y Pisinger 2004, p. 461
5. Kellerer, Pferschy y Pisinger 2004, p. 465
6. Kellerer, Pferschy y Pisinger 2004, p. 472
7. Feuerman, Martin; Weiss, Harvey (abril de 1973). "Un modelo de programación matemática para la construcción de pruebas y la puntuación". Ciencias de la gestión . 19 (8): 961–966. doi : 10.1287 / mnsc.19.8.961 . JSTOR 2629127 . 
8. Skiena, SS (septiembre de 1999). "¿Quién está interesado en algoritmos y por qué? Lecciones del repositorio de algoritmos de Stony Brook". Noticias ACM SIGACT . 30 (3): 65–74. CiteSeerX 10.1.1.41.8357 . doi : 10.1145 / 333623.333627 . ISSN 0163-5700 . S2CID 15619060 .   
9. Pisinger, D. 2003. ¿Dónde están los problemas de la mochila dura? Informe técnico 2003/08, Departamento de Ciencias de la Computación, Universidad de Copenhague, Copenhague, Dinamarca.
10. Caccetta, L .; Kulanoot, A. (2001). "Aspectos computacionales de los problemas de la mochila dura". Análisis no lineal . 47 (8): 5547–5558. doi : 10.1016 / s0362-546x (01) 00658-7 .
11. Poirriez, Vincent; Yanev, Nicola; Andonov, Rumen (2009). "Un algoritmo híbrido para el problema de la mochila sin límites". Optimización discreta . 6 (1): 110-124. doi : 10.1016 / j.disopt.2008.09.004 . ISSN 1572-5286 . 
12. Wojtczak, Dominik (2018). "Sobre la integridad NP fuerte de los problemas racionales". Simposio Internacional de Informática en Rusia . Apuntes de conferencias en Ciencias de la Computación. 10846 : 308–320. arXiv : 1802.09465 . doi : 10.1007 / 978-3-319-90530-3_26 . ISBN 978-3-319-90529-7. S2CID  3637366 .
13. Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). "Problema ilimitado de la mochila: revisión de la programación dinámica" . Revista europea de investigación operativa . 123 (2): 168-181. CiteSeerX 10.1.1.41.2135 . doi : 10.1016 / S0377-2217 (99) 00265-9 . ^{[ enlace muerto permanente ]}
14. S. Martello, P. Toth, Problemas de mochila: algoritmos e implementaciones informáticas, John Wiley and Sons, 1990
15. S. Martello, D. Pisinger, P. Toth, Programación dinámica y límites fuertes para el problema de la mochila 0-1 , Manag. Sci. 45: 414–424, 1999.
16. Plateau, G .; Elkihel, M. (1985). "Un algoritmo híbrido para el problema de la mochila 0-1". Métodos de operación. Res . 49 : 277-293.
17. Martello, S .; Toth, P. (1984). "Una mezcla de programación dinámica y bifurcación y límite para el problema de la suma de subconjuntos". Manag. Sci . 30 (6): 765–771. doi : 10.1287 / mnsc.30.6.765 .
18. Horowitz, Ellis; Sahni, Sartaj (1974), "particiones Informática con aplicaciones al problema de la mochila", revista de la Association for Computing Machinery , 21 (2): 277-292, doi : 10.1145 / 321,812.321823 , HDL : 1813/5989 , MR 0.354.006 , S2CID 16866858  
19. Vazirani, Vijay. Algoritmos de aproximación. Springer-Verlag Berlín Heidelberg, 2003.
20. Dantzig, George B. (1957). "Problemas de extremidades variables discretas". Investigación operativa . 5 (2): 266–288. doi : 10.1287 / opre.5.2.266 .
21. Chang, TJ, et al. Heurística para la optimización de carteras con restricciones de cardinalidad . Informe técnico, Londres SW7 2AZ, Inglaterra: The Management School, Imperial College, mayo de 1998
22. Chang, CS y col. " Optimización de bicriterio basada en algoritmos genéticos para subestaciones de tracción en sistemas ferroviarios de CC ". En Fogel [102], 11-16.
23. Kulik, A .; Shachnai, H. (2010). "No hay EPTAS para mochila bidimensional" (PDF) . Inf. Proceso. Lett . 110 (16): 707–712. CiteSeerX 10.1.1.161.5838 . doi : 10.1016 / j.ipl.2010.05.031 .  
24. Cohen, R. y Grebla, G. 2014. "Programación OFDMA multidimensional en una red inalámbrica con nodos de retransmisión" . en Proc. IEEE INFOCOM'14 , 2427–2435.
25. Yan Lan, György Dósa, Xin Han, Chenyang Zhou, Attila Benkő [1] : Mochila 2D: Cuadrados de embalaje , Informática teórica Vol. 508, págs. 35–40.
26. Chandra Chekuri y Sanjeev Khanna (2005). "Un PTAS para el problema de la mochila múltiple". Revista SIAM de Computación . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . doi : 10.1137 / s0097539700382820 . 
27. Wu, ZY; Yang, YJ; Bai, FS; Mammadov, M. (2011). "Condiciones de Optimidad Global y Métodos de Optimización para Problemas Cuadráticos de Mochila". J Optim Theory Appl . 151 (2): 241-259. doi : 10.1007 / s10957-011-9885-4 . S2CID 31208118 . 
28. Gallo, G .; Hammer, PL; Simeone, B. (1980). Problemas cuadráticos de la mochila . Estudios de Programación Matemática . 12 . págs. 132-149. doi : 10.1007 / BFb0120892 . ISBN 978-3-642-00801-6.
29. Witzgall, C. (1975). Métodos matemáticos de selección de sitios para sistemas de mensajes electrónicos (EMS) . Informe interno de NBS. Código Bib : 1975STIN ... 7618321W .
30. Richard M. Karp (1972). " Reducibilidad entre problemas combinatorios ". En RE Miller y JW Thatcher (editores). Complejidad de los cálculos informáticos. Nueva York: Pleno. págs. 85-103
31. Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). "El problema de la suma de subconjuntos múltiples" . SIAM J. Optim . 11 (2): 308–319. CiteSeerX 10.1.1.21.9826 . doi : 10.1137 / S1052623498348481 . 
32. Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A .; Wiese, Andreas (2015). "Sobre secuencias de corte de guillotina" : 1–19. doi : 10.4230 / LIPIcs.APPROX-RANDOM.2015.1 . ISBN 978-3-939897-89-7.

Referencias

• Garey, Michael R .; David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. ISBN 978-0-7167-1045-5. A6: MP9, pág.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila . Saltador. doi : 10.1007 / 978-3-540-24777-7 . ISBN 978-3-540-40286-2. Señor  2161720 .
• Martello, Silvano; Toth, Paolo (1990). Problemas de la mochila: Algoritmos e implementaciones informáticas . Wiley-Interscience. ISBN 978-0-471-92420-3. Señor  1086874 .

Enlaces externos

• Descarga gratuita del libro "Problemas de la mochila: Algoritmos e implementaciones informáticas", de Silvano Martello y Paolo Toth
• Diapositivas de conferencias sobre el problema de la mochila
• PYAsUKP: Otro solucionador más para el problema de la mochila ilimitada , con código que aprovecha las relaciones de dominio en un algoritmo híbrido, puntos de referencia y copias descargables de algunos artículos.
• Página de inicio de David Pisinger con copias descargables de algunos artículos de la lista de publicaciones (incluido "¿Dónde están los problemas de la mochila dura?")
• Soluciones de problemas de mochila en muchos idiomas en Rosetta Code
• Algoritmo de programación dinámica para el problema de la mochila 0/1
• Knapsack Problem solver (en línea)
• Resolviendo 0-1-KNAPSACK con algoritmos genéticos en Ruby Archivado el 23 de mayo de 2011 en la Wayback Machine.
• Códigos para el problema de la mochila cuadrática

• Optimización del embalaje de contenedores tridimensionales
• Solución de programación de enteros de mochila en Python Gekko (software de optimización)