Problema de la mochila cuadrática

El problema de la mochila cuadrática (QKP), introducido por primera vez en el siglo XIX,​ 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 beneficio adicional que se puede obtener si se seleccionan dos artículos concretos, determinar la cantidad de artículos que se incluirán 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áticos 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ático 0-1, que fue discutido por primera vez por Gallo et al.​ El problema de la mochila cuadrático 0-1 es una variación de los problemas de la mochila, que combina las características del problema de la mochila ilimitado, el problema de la mochila 0-1 y el problema de la mochila cuadrático.

Definición

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

${\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{ binario }}\right\}$

${\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{ para }}i=1,\ldots ,n\right\}.$

Aquí la variable binaria x _i representa si el artículo i está incluido en la mochila, $p_{i}$ es la ganancia obtenida al seleccionar el elemento i y $P_{ij}$ es el beneficio obtenido si se suman los elementos i y j .

Informalmente, 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.

Aplicación

Como era de esperar, QKP tiene una amplia gama de aplicaciones que incluyen telecomunicaciones, redes de transporte, informática y economía. De hecho, Witzgall analizó por primera vez QKP al seleccionar lugares para ubicar estaciones de ferrocarril secundarias con el fin de 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 manipulación de carga.​ Las aplicaciones de QKP en el campo de la informática son más comunes después de los primeros tiempos de su desarrollo: problemas de diseño de compiladores,​ problema de camarilla,​​ diseño de integración a muy gran escala (VLSI).​ Además, los problemas de precios parecen ser una aplicación de QKP como lo describen Johnson et al.​

Complejidad computacional

En general, la versión de decisión del problema de la mochila (¿Se puede alcanzar un valor de al menos V bajo una restricción de una determinada capacidad W?) es NP-completa .​ Por lo tanto, una solución dada se puede verificar 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-difícil y no existe ningún algoritmo conocido que pueda resolver el problema en tiempo polinomial.

Como variación particular del problema de la mochila, el problema de la mochila cuadrático 0-1 también es NP-difícil.

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

Resolviendo

Si bien el problema de la mochila es uno de los problemas de investigación operativa (OR) más comúnmente resueltos, existen algoritmos eficientes limitados que pueden resolver problemas de mochila cuadráticos 0-1. Los algoritmos disponibles incluyen, entre otros, fuerza bruta, linealización,​ y reformulación convexa. Al igual que otros problemas NP-difíciles, suele ser suficiente encontrar una solución viable aunque no sea necesariamente óptima. Algoritmos heurísticos basados en algoritmos codiciosos, la programación dinámica puede brindar una solución relativamente "buena" al QKP 0-1 de manera eficiente.

Fuerza bruta

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

// Aporte:
//     Ganancias (almacenadas en la matriz p)
//     Beneficios cuadráticos (almacenados en la matriz P)
//     Pesos (almacenados en la matriz w)
//     Número de elementos (n)
//     Capacidad de la mochila (W)

En t máximo = 0
para todo subconjunto S hacer
    en t valor, peso = 0
    para i de 0 a S. tamaño -1 hacer:
        valor = valor + p[i]
        peso = peso + w[i]
            para j de i+1 a S. tamaño -1 hacer: 
                valor = valor + P[i][j]
    si peso <= W entonces:
        si valor > máximo entonces:    
            máximo = valor

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

$(2^{n}n^{2})=\lambda (2^{n})$, siendo exponencial.

Linealización

Los problemas de este tipo son difíciles de resolver directamente utilizando solucionadores estándar y, por lo tanto, la gente intenta reformularlo como un programa lineal utilizando variables auxiliares y restricciones para que el problema pueda resolverse fácilmente utilizando paquetes comerciales. Dos enfoques de linealización bien conocidos para el QKP 0-1 son la linealización estándar y la linealización de Glover.​​​

Linealización estándar

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

LP1: maximizar

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

sujeto a

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

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

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

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

$x\in 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 la mochila, que luego podemos resolver de manera óptima utilizando solucionadores estándar.

Linealización de Glover

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

$\sum _{j=1,i\neq j}^{n}P_{ij}x_{j}$, respectivamente:

LP2: maximizar

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

sujeto a

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

$\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 $i=1,\ldots ,n$

$x\in X,x$ binario

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

Reformulación cuadrática convexa

Tenga en cuenta que los programas no lineales son difíciles de resolver debido a la posibilidad de quedar atrapados en un máximo local . Sin embargo, cuando el programa es convexo, cualquier máximo local es el máximo global . Un programa convexo consiste en maximizar una función cóncava o minimizar una función convexa en un conjunto convexo . Un conjunto S es convexo si $\forall u,v\in S$, $\lambda u+(1-\lambda )v\in S$ dónde $\lambda \in [0,1]$ . Es decir, cualquier punto entre dos puntos del conjunto también debe ser un elemento del conjunto. Una función f es cóncava si $f[\lambda u+(1-\lambda )v]\leq \lambda f(u)+(1-\lambda )f(v)$ . Una función f es convexa si $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 recta que conecta dos puntos en la gráfica se encuentra arriba o sobre la gráfica, mientras que una función es convexa si está debajo o sobre la gráfica. 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 $c^{T}x+x^{T}Cx$ usando notación de álgebra lineal. Necesitamos hacer de P una matriz semidefinida positiva para reformular una función convexa. En este caso, modificamos la función objetivo para que sea $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})$ aplicando resultados de álgebra lineal, donde P es una matriz diagonalmente dominante y, por tanto, una semidefinida positiva. Esta reformulación se puede resolver utilizando un paquete cuadrático entero mixto comercial estándar.​

Algoritmo heurístico codicioso

George Dantzig​ propuso un algoritmo de aproximación codiciosa al problema de la mochila ilimitado que también puede usarse para resolver el QKP 0-1. El algoritmo consta de dos frases: identificar una solución inicial y mejorarla.

Primero calcule para cada elemento, la contribución objetiva total realizable al seleccionarlo, $p_{i}+\sum _{i\neq j}^{n}P_{ij}$ y clasifique los artículos en orden decreciente del valor potencial por unidad de peso, $(p_{i}+\sum _{i\neq j}^{n}P_{ij})/w_{i}$ . Luego seleccione los artículos con la máxima relación valor-peso en la mochila hasta que no haya espacio para más, lo que constituye la solución inicial. A partir de la solución inicial, la mejora se realiza mediante intercambio por pares. Para cada elemento del conjunto de soluciones, identifique los elementos que no están en el conjunto donde el intercambio da como resultado un objetivo de mejora. Seleccione el par con máxima mejora e intercambie. 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 ningún intercambio mejorado. La clase de complejidad de este algoritmo es $O(2^{n})$ ya que para el peor de los casos se identificarán todas las combinaciones posibles de elementos.

cuádruple

Quadknap es un algoritmo exacto de rama y límite propuesto por Caprara et al.,​ donde los límites superiores se calculan considerando una relajación lagrangiana que aproxima un problema difícil mediante un problema más simple y penaliza las violaciones de restricciones utilizando el multiplicador de Lagrange para imponer un costo por violaciones. Quadknap libera el requisito de números enteros al calcular los límites superiores. Los multiplicadores lagrangianos subóptimos se derivan de la optimización de subgradiente 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 aquellas que pueden resolverse mediante otros enfoques. El código fue escrito en C y está disponible en línea.​

Heurística de programación dinámica

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​ sólo pueden producir una solución de calidad relativamente buena, que puede servir como límite inferior para los objetivos óptimos. Si bien se ejecuta en tiempo pseudopolinomial, requiere una gran cantidad de memoria.

Algoritmo de programación dinámica

Para simplificar, supongamos que todas las ponderaciones no son negativas. El objetivo es maximizar el valor total sujeto a la restricción: que el peso total sea menor o igual a W. Luego para cada $w\leq W$, definir $f(m,w)$ ser el valor del embalaje más rentable de los primeros m artículos encontrados con un peso total de w . Es decir, deja

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

Entonces, $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, comienza con el primer artículo e intenta encontrar un mejor empaque considerando agregar artículos con un peso esperado de 𝑤. Si el peso del elemento que se va a agregar excede 𝑤, entonces $f(m,w)$ es lo mismo con $f(m-1,w)$ . Dado que el artículo tiene un peso menor en comparación con el peso deseado, $f(m,w)$ es lo mismo que $f(m-1,w)$ si sumar no aporta nada, o la misma solución que para una mochila de menor capacidad, concretamente una con la capacidad reducida por el peso de ese artículo elegido, más el valor de un artículo correcto, es decir $f(m-1,w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}$ . Para concluir tenemos que

$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}&{\text{ si }}w_{m}\leq w\\f(m-1,w)&{\text{ en caso contrario}}\end{cases}}$

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

Algoritmo de programación dinámica revisado

Tenga en cuenta que el algoritmo anterior requiere $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 eliminando el índice m de $f(m,w)$ ya que todos los cálculos dependen únicamente de los resultados de la etapa anterior.

Redefinir $f(w)$ ser el valor actual del embalaje más rentable encontrado por la heurística. Eso es,

$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\right\}.$

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

$f(m)={\begin{cases}\max f(w),f(w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}&{\text{ si }}w_{m}\leq w,\\f(w)&{\text{ en otro caso.}}\end{cases}}$

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

Temas de investigación relacionados

Los investigadores han estudiado problemas de la mochila cuadráticos 0-1 durante décadas. Un objetivo es encontrar algoritmos o heurísticas eficaces, especialmente aquellos con un rendimiento excepcional para resolver problemas del mundo real. La relación entre la versión de decisión y la versión de optimización del QKP 0-1 no debe ignorarse cuando se trabaja con cualquiera de ellas. 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 se puede utilizar 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 QKP 0-1 suelen realizar estudios computacionales​ para mostrar la superioridad de sus estrategias. Estos estudios también se pueden realizar para evaluar el rendimiento de diferentes métodos de solución. Para el QKP 0-1, esos estudios computacionales a menudo se basan en datos generados aleatoriamente, presentados por Gallo et al. Básicamente, todos los estudios computacionales del QKP 0-1 utilizan datos que se generan aleatoriamente de la siguiente manera. Las ponderaciones son números enteros tomados de una distribución uniforme en el intervalo [1, 50], y las restricciones de capacidad son un número entero tomado de una distribución uniforme entre 50 y la suma de las ponderaciones de los elementos. Los coeficientes objetivos, es decir, los valores, se eligen aleatoriamente entre [1100]. Se ha observado que generar instancias de esta forma produce problemas con dificultad muy variable e impredecible. Por lo tanto, los estudios computacionales presentados en la literatura pueden no ser sólidos. Así, algunas investigaciones pretenden desarrollar una metodología para generar instancias del QKP 0-1 con un nivel de dificultad predecible y consistente.

Véase también

• Portal:Programación. Contenido relacionado con Programación.
• Problema de la mochila
• Subasta combinatoria
• Optimización combinatoria
• Problema continuo de la mochila
• Anexo:Problemas de la mochila
• Problema de empaquetado

Enlaces externos

• Datos: Q28001197