Problema de la mochila - Knapsack problem

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 a 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 limitació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. El nombre "problema de la mochila" se remonta a los primeros trabajos del matemático Tobias Dantzig (1884-1956), y se refiere al lugar común problema 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, selección de inversiones y carteras , selección de activos para titulización respaldada por activos y generación de claves para el Merkle – Hellman y otros criptosistemas de mochila .

Una de las primeras aplicaciones de los algoritmos de 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 de puntos totales suman 100, un algoritmo de mochila determinaría qué subconjunto da a cada estudiante la puntuación más alta posible.

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 .

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 limitada ( 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 exactamente.

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 la 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 las instancias "difíciles" del problema de la mochila, o verlas de otra manera, para identificar qué propiedades de las instancias en la práctica podrían hacerlas más dóciles de lo que sugiere su comportamiento NP-completo en el peor de los casos. 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 fuertemente NP-completo si los pesos y las ganancias se dan como números racionales. Sin embargo, en el caso de pesos y ganancias racionales, todavía admite un esquema de aproximación de tiempo completamente polinomial .

Resolviendo

Se encuentran disponibles varios algoritmos para resolver problemas de mochila, basados ​​en el enfoque de programación dinámica, el enfoque de bifurcación y enlace o hibridaciones de ambos enfoques.

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 artículos 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]}$${\ 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:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

array m[0..n, 0..W];
for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    m[i, 0] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            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})}$

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

Define value[n, W]

Initialize all value[i, j] = -1

Define m:=(i,j)         // Define function m so that it represents the maximum value we can get under the condition: use first i items, total weight limit is j
{
    if i == 0 or j <= 0 then:
        value[i, j] = 0
        return

    if (value[i-1, j] == -1) then:     // m[i-1, j] has not been calculated, we have to call function m
        value[i-1, j] = m(i-1, j)

    if w[i] > j then:                      // item cannot fit in the bag
        value[i, j] = value[i-1, j]
    else: 
        if (value[i-1, j-w[i]] == -1) then:     // m[i-1,j-w[i]] has not been calculated, we have to call function m
            value[i-1, j-w[i]] = m(i-1, j-w[i])
        value[i, j] = max(value[i-1,j], value[i-1, j-w[i]] + v[i])
}

Run m(n, W)

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

${\ displaystyle {\ begin {alineado} & 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 {alineado}}}$

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 {alineado} & 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 {alineado}}}$

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:

/**
 * Returns the indices of the items of the optimal knapsack.
 * i: We can include items 1 through i in the knapsack
 * j: maximum weight of the knapsack
 */
function knapsack(i: int, j: int): Set<int> {
    if i == 0 then:
        return {}
    if m[i, j] > m[i-1, j] then:
        return {i} ∪ knapsack(i-1, j-w[i])
    else:
        return knapsack(i-1, j)
}

knapsack(n, W)

Encontrarse en el medio

Otro algoritmo para la mochila 0-1, descubierto en 1974 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 al algoritmo DP. cuando es grande comparado 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, será necesario 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})}$

algorithm Meet-in-the-middle is
    input: A set of items with weights and values.
    output: The greatest combined value of a subset.

    partition the set {1...n} into two sets A and B of approximately equal size
    compute the weights and values of all subsets of each set

    for each subset of A do
        find the subset of B of greatest value such that the combined weight is less than W

    keep track of the greatest combined value seen so far

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, es uno de una colección de algoritmos que aún pueden aproximarse 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).

Algoritmo de aproximación codicioso

George Dantzig propuso un algoritmo de aproximación codicioso para resolver el problema ilimitado de la mochila. Su versión ordena los elementos 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 acotado, 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: Supongamos por simplicidad que todos los elementos caben individualmente en el saco ( para todos ). Construya 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 w_ {i} \ leq W}$${\ Displaystyle i}$${\ 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.

algorithm FPTAS is 
    input: ε ∈ (0,1]
            a list A of n items, specified by their values, ${\displaystyle v_{i}}$, and weights
    output: S' the FPTAS solution

    P := max ${\displaystyle \{v_{i}\mid 1\leq i\leq n\}}$  // the highest item value
    K := ε ${\displaystyle {\frac {P}{n}}}$

    for i from 1 to n do
        ${\displaystyle v'_{i}}$ := ${\displaystyle \left\lfloor {\frac {v_{i}}{K}}\right\rfloor }$
    end for

    return the solution, S', using the ${\displaystyle v'_{i}}$ values in the dynamic program outlined above

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

Relaciones de dominancia

La solución del problema ilimitado de la mochila puede ser más fácil desechando artículos que nunca serán necesarios. Para un elemento dado , suponga que podemos encontrar un conjunto de elementos 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 , y todas satisfacen 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 \ en 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 y utilizada por primera vez 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

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 artículos, el número de objetivos o incluso el número de mochilas.

Problema de la 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 la optimización de la logística de transporte y la cartera.

Como 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. Sin embargo, se muestra que el algoritmo en 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. El algoritmo de también resuelve instancias escasas de la variante de opción múltiple, mochila multidimensional de opción múltiple. ${\ Displaystyle D = 2}$${\ displaystyle =}$${\ Displaystyle J = \ {1,2, \ ldots, m \}}$${\ Displaystyle m <D}$${\ Displaystyle i}$${\ Displaystyle \ existe 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.

Problema de mochila múltiple

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 .

Problema de la mochila cuadrática

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

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 . ${\ 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 .

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.

Ver también

Notas

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)