LISTA DE PROBLEMAS

El problema de la mochila cuadrática (QKP) , introducido por primera vez en el siglo XIX, ^[1] es una extensión del problema de la mochila que permite términos cuadráticos en la función objetivo: dado un conjunto de elementos, cada uno con un peso, un valor y un extra beneficio que se puede obtener si se seleccionan dos artículos, determine el número de artículos a incluir en una colección sin exceder la capacidad de la mochila , para maximizar el beneficio general. Por lo general, los problemas de la mochila cuadrática vienen con una restricción en el número de copias de cada tipo de artículo: 0 o 1. Este tipo especial de QKP forma el problema de la mochila cuadrática 0-1 , que fue discutido por primera vez por Gallo et al. ^[2] El problema de la mochila cuadrática 0-1 es una variación de los problemas de la mochila, combinando las características del problema de la mochila sin límites, el problema de la mochila 0-1 y el problema de la mochila cuadrática.

Definición [ editar ]

Específicamente, el problema de la mochila cuadrática 0-1 tiene la siguiente forma:

$${\ displaystyle {\ text {maximizar}} \ left \ {\ sum _ {i = 1} ^ {n} p_ {i} x_ {i} + \ sum _ {i = 1} ^ {n} \ sum _ {j = 1, i \ neq j} ^ {n} P_ {ij} x_ {i} x_ {j}: x \ in X, x {\ text {binary}} \ right \}}

$${\ displaystyle {\ text {sujeto a}} X \ equiv \ left \ {x \ in \ {0,1 \} ^ {n}: \ sum _ {i = 1} ^ {n} w_ {i} x_ {i} \ leq W; x_ {i} \ in \ {0,1 \} {\ text {for}} i = 1, \ ldots, n \ right \}.}

Mientras que la variable binaria x _i representa si el ítem i está incluido en la mochila,$${\ displaystyle p_ {i}}es el beneficio obtenido por el elemento de selección i y$${\ displaystyle P_ {ij}}es el beneficio obtenido si ambos elemento i y j se añaden.

Informalmente, el problema es maximizar la suma de los valores de los artículos en la mochila para que la suma de los pesos sea menor o igual que la capacidad de la mochila.

Solicitud [ editar ]

Como era de esperar, QKP tiene una amplia gama de aplicaciones que incluyen telecomunicaciones , red de transporte , informática y economía . De hecho, Witzgall primero discutió QKP cuando seleccionó sitios para estaciones satelitales para maximizar el tráfico global con respecto a una restricción presupuestaria. Un modelo similar se aplica a problemas como considerar la ubicación de aeropuertos, estaciones de ferrocarril o terminales de manejo de carga. ^[3] Las aplicaciones de QKP en el campo de la informática son más comunes después de los primeros días: problema de diseño del compilador , ^[4] problema de camarilla , ^[5] [6] integración a gran escala(VLSI) diseño. ^[7] Además, los problemas de precios parecen ser una aplicación de QKP según lo descrito por Johnson et al. ^[8]

Complejidad computacional [ editar ]

En general, la versión de decisión del problema de la mochila (¿Se puede lograr un valor de al menos V bajo una restricción de cierta capacidad W?) Es NP-completa . ^[9] Por lo tanto, se puede verificar una solución dada en tiempo polinómico, mientras que ningún algoritmo puede identificar una solución de manera eficiente.

El problema de la mochila de optimización es NP-hard y no existe un algoritmo conocido que pueda resolver el problema en tiempo polinómico.

Como una variación particular del problema de la mochila, el problema de la mochila cuadrática 0-1 también es NP-duro.

Si bien no existe un algoritmo eficiente disponible en la literatura, existe un tiempo pseudo-polinomial basado en programación dinámica y otros algoritmos heurísticos que siempre pueden generar soluciones "buenas".

Resolviendo [ editar ]

Si bien el problema de la mochila es uno de los problemas de investigación de operación (OR) más comúnmente resueltos , existen algoritmos eficientes limitados que pueden resolver problemas de mochila de 0-1 cuadráticos. Algoritmos disponibles incluyen pero no se limitan a la fuerza bruta , linealización , ^[10] y reformulación convexa. Al igual que otros problemas difíciles de NP, generalmente es suficiente encontrar una solución viable, incluso si no es necesariamente óptima. Algoritmos heurísticos basados ​​en un algoritmo codicioso , la programación dinámica puede dar una solución relativamente "buena" al 0-1 QKP de manera eficiente.

Fuerza bruta [ editar ]

El algoritmo de fuerza bruta para resolver este problema es identificar todos los subconjuntos posibles de los elementos sin exceder la capacidad y seleccionar el que tenga el valor óptimo. El pseudocódigo se proporciona de la siguiente manera:

1 // Entrada: 
2 // Beneficios (almacenados en la matriz p) 
3 // Beneficios cuadráticos (almacenados en la matriz P) 
4 // Pesos (almacenados en la matriz w) 
5 // Número de artículos (n) 
6 // Capacidad de la mochila (W) 
7 
8 int  max  = 0 
9 para  todos los  subconjuntos  S  hacer 
10 	int  valor ,  peso  =  0 
11  	para  i  desde  0  a  S . tamaño - 1  do : 
valor 12		 =  Valor  + p [ i ] 
13 		peso  =  peso  + w [ i ] 
14 			para  j  desde  i + 1  a  S . tamaño - 1  do :  
15 				valor  =  valor  +  P [ i ] [ j ] 
16 	si  peso  <=  W  entonces : 
17 		si  valor  >  max  entonces :	
18 			max  =  valor

Dado n elementos, habrá como máximo$${\ displaystyle 2 ^ {n}} subconjuntos y para cada conjunto de candidatos legales, el tiempo de ejecución de calcular los valores obtenidos es $${\ displaystyle O (n ^ {2})}. Por lo tanto, la clase de eficiencia del algoritmo de fuerza bruta es$${\ displaystyle (2 ^ {n} n ^ {2}) = \ lambda (2 ^ {n})}, siendo exponencial.

Linealización [ editar ]

Los problemas de esta forma son difíciles de resolver directamente usando solucionadores estándar y, por lo tanto, las personas intentan reformularlo como un programa lineal usando variables y restricciones auxiliares para que el problema pueda resolverse fácilmente usando paquetes comerciales. Dos enfoques de linealización bien conocidos para el 0-1 QKP son la linealización estándar y la linealización de Glover. ^{[11] [12] [13]}

Linealización estándar [ editar ]

La primera es la estrategia de linealización estándar, como se muestra a continuación:

LP1: maximizar

$${\ displaystyle \ sum _ {i = 1} ^ {n} p_ {i} x_ {i} + \ sum _ {i = 1} ^ {n} \ left (\ sum _ {j = 1, i \ neq j} ^ {n} (P_ {ij} + P_ {ji}) z_ {ij} \ right).}

sujeto a

$${\ displaystyle z_ {ij} \ leq x_ {i}} para todos {\ displaystyle (i, j), i

$${\ displaystyle z_ {ij} \ leq x_ {j}} para todos {\ displaystyle (i, j), i

$${\ displaystyle x_ {i} + x_ {j} -1 \ leq z_ {ij}} para todos {\ displaystyle (i, j), i

$${\ displaystyle z_ {ij} \ geq 0} para todos {\ displaystyle (i, j), i

$${\ displaystyle x \ en X, x} binario

En la formulación LP1, hemos reemplazado el término x _i x _j con una variable continua z _ij . Esto reformula el QKP en un problema de mochila, que luego podemos resolver de manera óptima utilizando solucionadores estándar.

Linealización de Glover [ editar ]

La segunda reformulación, que es más concisa, se llama linealización de Glover. ^{[14] [15] [16]} La formulación de Glover se muestra a continuación, donde L _i y U _i son los límites inferior y superior en$${\ displaystyle \ sum _ {j = 1, i \ neq j} ^ {n} P_ {ij} x_ {j}}, respectivamente:

LP2: maximizar

$${\ displaystyle \ sum _ {i = 1} ^ {n} p_ {i} x_ {i} + \ sum _ {i = 1} ^ {n} z_ {i}}

sujeto a

$${\ displaystyle L_ {i} x_ {i} \ leq z_ {i} \ leq U_ {i} x_ {i}} para $${\ displaystyle i = 1, \ ldots, n}

$${\ displaystyle \ sum _ {j = 1, i \ neq j} ^ {n} P_ {ij} x_ {j} -U_ {i} (1-x_ {i}) \ leq z_ {i} \ leq \ sum _ {j = 1, i \ neq j} ^ {n} P_ {ij} x_ {j} -L_ {i} (1-x_ {i})} para $${\ displaystyle i = 1, \ ldots, n}

$${\ displaystyle x \ en X, x} binario

En la formulación LP2, hemos reemplazado la expresión $${\ displaystyle \ sum _ {j = 1, i \ neq j} ^ {n} P_ {ij} x_ {i} x_ {j}} con una variable continua z _i . Del mismo modo, podemos usar solucionadores estándar para resolver el problema de linealización. Tenga en cuenta que la linealización de Glover solo incluye$${\ displaystyle n} variables auxiliares con $${\ displaystyle 2n} restricciones, mientras que la linealización estándar requiere $${\ displaystyle {n \ choose 2}} variables auxiliares y $${\ displaystyle 3 {n \ choose 2}} restricciones para lograr la linealidad.

Reformulación cuadrática convexa [ editar ]

Tenga en cuenta que los programas no lineales son difíciles de resolver debido a la posibilidad de estar atascado en un máximo local . Sin embargo, cuando el programa es convexo , cualquier máximo local es el máximo global . Un programa convexo es maximizar una función cóncava o minimizar una función convexa en un conjunto convexo . Un conjunto S es convexo si$${\ displaystyle \ para todos, v \ en S}, $${\ displaystyle \ lambda u + (1- \ lambda) v \ en S} dónde $${\ displaystyle \ lambda \ en [0,1]}. Es decir, cualquier punto entre dos puntos en el conjunto también debe ser un elemento del conjunto. Una función f es cóncava si$${\ displaystyle f [\ lambda u + (1- \ lambda) v] \ leq \ lambda f (u) + (1- \ lambda) f (v)}. Una función f es convexa si$${\ displaystyle f [\ lambda u + (1- \ lambda) v] \ geq \ lambda f (u) + (1- \ lambda) f (v)}. Informalmente, una función es cóncava si el segmento de línea que conecta dos puntos en el gráfico se encuentra arriba o en el gráfico, mientras que una función es convexa si está debajo o en el gráfico. Por lo tanto, al reescribir la función objetivo en una función convexa equivalente, podemos reformular el programa para que sea convexo, lo que se puede resolver utilizando paquetes de optimización.

La función objetivo se puede escribir como $${\ displaystyle c ^ {T} x + x ^ {T} Cx}usando notación de álgebra lineal. Necesitamos hacer de P una matriz semi-definida positiva para reformular una función convexa. En este caso, modificamos la función objetivo para que sea$${\ displaystyle p ^ {T} x + x ^ {T} Px + \ sum _ {i = 1} ^ {n} \ left (\ sum _ {j = 1, j \ neq i} ^ {n} | P_ {ij} | \ right) (x_ {i} ^ {2} -x_ {i})}mediante la aplicación de resultados del álgebra lineal, donde P es una matriz diagonalmente dominante y, por lo tanto, una semi-definida positiva. Esta reformulación puede resolverse usando un paquete cuadrático comercial de enteros mixtos estándar. ^[17]

Algoritmo heurístico codicioso [ editar ]

George Dantzig ^[18] propuso un algoritmo de aproximación codicioso para un problema de mochila sin límites que también se puede utilizar para resolver el 0-1 QKP. El algoritmo consta de dos frases: identificar una solución inicial y mejorarla.

Primero calcule para cada elemento, la contribución objetiva total realizable seleccionándola, $${\ displaystyle p_ {i} + \ sum _ {i \ neq j} ^ {n} P_ {ij}}, y clasifique los elementos en orden decreciente del valor potencial por unidad de peso, $${\ displaystyle (p_ {i} + \ sum _ {i \ neq j} ^ {n} P_ {ij}) / w_ {i}}. Luego seleccione los artículos con la relación valor-peso máxima en la mochila hasta que no haya espacio para más, lo que forma la solución inicial. Comenzando con la solución inicial, la mejora se lleva a cabo mediante intercambio por pares. Para cada elemento del conjunto de soluciones, identifique los elementos que no están en el conjunto donde el intercambio resulta en un objetivo de mejora. Seleccione el par con la mejora máxima y el intercambio. También hay posibilidades de que eliminar uno del conjunto o agregar uno al conjunto produzca la mayor contribución. Repita hasta que no haya mejor intercambio. La clase de complejidad de este algoritmo es$${\ displaystyle O (2 ^ {n})} ya que para el peor de los casos se identificarán todas las combinaciones posibles de artículos.

Quadknap [ editar ]

Quadknap es un algoritmo exacto de ramificación y unión planteado por Caprara et al., ^[19] donde los límites superiores se calculan considerando una relajación lagrangiana que se aproxima a un problema difícil por un problema más simple y penaliza las violaciones de restricciones utilizando el multiplicador Lagrangepara imponer un costo a las violaciones. Quadknap libera el requisito de enteros al calcular los límites superiores. Los multiplicadores lagrangianos subóptimos se derivan de la optimización del subdegradado y proporcionan una reformulación conveniente del problema. Este algoritmo es bastante eficiente ya que los multiplicadores lagrangianos son estables y se adoptan estructuras de datos adecuadas para calcular un límite superior ajustado en el tiempo lineal esperado en el número de variables. Se informó que este algoritmo genera soluciones exactas de instancias con hasta 400 variables binarias, es decir, significativamente más grandes que las que se pueden resolver con otros enfoques. El código fue escrito en C y está disponible en línea. ^[20]

Programación dinámica heurística [ editar ]

Si bien la programación dinámica puede generar soluciones óptimas a los problemas de la mochila, los enfoques de programación dinámica para QKP ^[21] solo pueden proporcionar una solución de calidad relativamente buena, que puede servir como un límite inferior para los objetivos óptimos. Si bien se ejecuta en tiempo pseudo-polinomial, tiene un gran requisito de memoria.

Algoritmo de programación dinámica [ editar ]

Por simplicidad, suponga que todos los pesos no son negativos. El objetivo es maximizar el valor total sujeto a la restricción: que el peso total es menor o igual a W . Entonces para cada$${\ displaystyle w \ leq W}, definir $${\ displaystyle f (m, w)}para ser el valor del embalaje más rentable de los primeros m elementos encontrados con un peso total de w . Es decir, deja

$${\ displaystyle f (m, w) = \ max \ left \ {\ sum _ {i = 1} ^ {m} p_ {i} x_ {i} + \ sum _ {i = 1} ^ {m} \ sum _ {j = 1, i \ neq j} ^ {m} P_ {ij} x_ {i} x_ {j}: \ sum _ {i = 1} ^ {m} w_ {i} = w, 1 \ leq i \ leq m \ right \}.}

Luego, $${\ displaystyle f (m, w)}Es la solución al problema. Tenga en cuenta que mediante la programación dinámica, la solución a un problema surge de la solución a sus subproblemas más pequeños. En este caso particular, comience con el primer artículo e intente encontrar un mejor embalaje considerando agregar artículos con un peso esperado de 𝑤. Si el peso del artículo a agregar excede 𝑤 , entonces$${\ displaystyle f (m, w)} es lo mismo con $${\ displaystyle f (m-1, w)}. Dado que el artículo tiene un peso menor en comparación con el peso deseado,$${\ displaystyle f (m, w)} es lo mismo que $${\ displaystyle f (m-1, w)} si agregar no contribuye, o es lo mismo que la solución para una mochila con menor capacidad, específicamente una con la capacidad reducida por el peso de ese artículo elegido, más el valor de un artículo correcto, es decir $${\ displaystyle f (m-1, w-w_ {m}) + p_ {m} + \ sum _ {i = 1} ^ {m-1} P_ {im} x_ {i}}. Para concluir, tenemos que

{\ displaystyle f (m, w) = {\ begin {cases} \ max f (m-1, w), f (m-1, w-w_ {m}) + p_ {m} + \ sum _ { i = 1} ^ {m-1} P_ {im} x_ {i} y {\ text {if}} w_ {m} \ leq w \\ f (m-1, w) & {\ text {de lo contrario} } \ end {casos}}}

Nota sobre la clase de eficiencia: claramente el tiempo de ejecución de este algoritmo es $${\ displaystyle O (Wn ^ {2})}, basado en el bucle anidado y el cálculo de la ganancia del nuevo empaque. Esto no contradice el hecho de que QKP es NP-hard ya que W no es polinomial en la longitud de la entrada.

Algoritmo de programación dinámica revisado [ editar ]

Tenga en cuenta que el algoritmo anterior requiere $${\ displaystyle O (Wn ^ {2})}espacio para almacenar el embalaje actual de artículos para todos los m, w , que pueden no ser capaces de manejar problemas de gran tamaño. De hecho, esto se puede mejorar fácilmente al eliminar el índice m de$${\ displaystyle f (m, w)} ya que todos los cálculos dependen solo de los resultados de la etapa anterior.

Redefinir $${\ displaystyle f (w)}ser el valor actual del embalaje más rentable encontrado por la heurística. Es decir,

$${\ displaystyle f (w) = \ max \ left \ {\ sum _ {i = 1} ^ {m} p_ {i} x_ {i} + \ sum _ {i = 1} ^ {m} \ sum _ {j = 1, i \ neq j} ^ {m} P_ {ij} x_ {i} x_ {j}: \ sum _ {i = 1} ^ {m} w_ {i} = w, m \ leq n \Derecha\}.}

En consecuencia, por programación dinámica tenemos que

{\ displaystyle f (m) = {\ begin {cases} \ max f (w), f (w-w_ {m}) + p_ {m} + \ sum _ {i = 1} ^ {m-1} P_ {im} x_ {i} y {\ text {if}} w_ {m} \ leq w, \\ f (w) y {\ text {de lo contrario.}} \ End {cases}}}

Tenga en cuenta que este algoritmo revisado todavía se ejecuta en $${\ displaystyle O (Wn ^ {2})} mientras solo toma $${\ displaystyle O (Wn)} memoria en comparación con el anterior $${\ displaystyle O (Wn ^ {2})}.

Temas de investigación relacionados [ editar ]

Los investigadores han estudiado 0-1 problemas de mochila cuadrática durante décadas. Un enfoque es encontrar algoritmos efectivos o heurísticas efectivas, especialmente aquellas con un rendimiento sobresaliente para resolver problemas del mundo real. La relación entre la versión de decisión y la versión de optimización del 0-1 QKP no debe ignorarse al trabajar con cualquiera de ellos. Por un lado, si el problema de decisión se puede resolver en tiempo polinómico, entonces se puede encontrar la solución óptima aplicando este algoritmo de forma iterativa. Por otro lado, si existe un algoritmo que puede resolver el problema de optimización de manera eficiente, entonces puede utilizarse para resolver el problema de decisión comparando la entrada con el valor óptimo.

Otro tema en la literatura es identificar cuáles son los problemas "difíciles". Los investigadores que estudian el 0-1 QKP a menudo realizan estudios computacionales ^[22] para mostrar la superioridad de sus estrategias. Dichos estudios también se pueden realizar para evaluar el rendimiento de diferentes métodos de solución. Para el 0-1 QKP, esos estudios computacionales a menudo se basan en datos generados al azar, introducidos por Gallo et al. Esencialmente, cada estudio computacional del 0-1 QKP utiliza datos que se generan aleatoriamente de la siguiente manera. Los pesos son enteros tomados de una distribución uniforme.durante el intervalo [1, 50], y las restricciones de capacidad es un número entero tomado de una distribución uniforme entre 50 y la suma de los pesos de los artículos. Los coeficientes objetivos, es decir, los valores se eligen aleatoriamente entre [1.100]. Se ha observado que generar instancias de esta forma genera problemas con dificultades muy variables e impredecibles. Por lo tanto, los estudios computacionales presentados en la literatura pueden ser poco sólidos. Por lo tanto, algunas investigaciones apuntan a desarrollar una metodología para generar instancias del 0-1 QKP con un nivel de dificultad predecible y constante.