Hispanopedia Wiki
Articulo de referencia

Problema de la mochila cuadrática

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 l...

Hispanopedia WikiContenido en espanolLectura gratuita

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 artículos, cada uno con un peso, un valor y una ganancia adicional que se puede obtener si se seleccionan dos artículos, determinar la cantidad de artículos a incluir en una colección sin exceder la capacidad de la mochila , para maximizar la ganancia total. Por lo general, los problemas de la mochila cuadrática vienen con una restricción en la cantidad 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 del problema de la mochila, que combina las características del problema de la mochila 0-1 y el problema de la mochila cuadrática.

Definición

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

maximizar {∑i=1nortepagiincógnitai+∑i=1norte∑j=1,i≠jnortePAGijincógnitaiincógnitaj:incógnita∈incógnita,incógnita binario}{\displaystyle {\text{maximize }}\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\}}
sujeto a incógnita≡{incógnita∈{0,1}norte:∑i=1nortewiincógnitai≤W;incógnitai∈{0,1} para i=1,…,norte}.{\displaystyle {\text{subject to }}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\}.}

Aquí la variable binaria x i representa si el artículo i está incluido en la mochila,pagi{\displaystyle p_{i}}es la ganancia obtenida al seleccionar el artículo i yPAGij{\displaystyle P_{ij}}es la ganancia obtenida si se agregan los artículos i y j .

De manera informal, el problema consiste en maximizar la suma de los valores de los objetos que contiene la mochila, de modo que la suma de los pesos sea menor o igual a la capacidad de la mochila.

Solicitud

Como cabría esperar, QKP tiene una amplia gama de aplicaciones, incluyendo telecomunicaciones , redes de transporte , informática y economía . De hecho, Witzgall fue el primero en hablar de QKP al seleccionar emplazamientos para estaciones satelitales con el fin de maximizar el tráfico global con respecto a una restricción presupuestaria. Un modelo similar se aplica a problemas como la consideración de la ubicación de aeropuertos, estaciones de ferrocarril o terminales de manipulación de carga. [ 3 ] Las aplicaciones de QKP en el campo de la informática son más comunes después de sus inicios: problema de diseño de compiladores , [ 4 ] problema de clique , [ 5 ] [ 6 ] diseño de integración a muy gran escala (VLSI). [ 7 ] Además, los problemas de precios parecen ser una aplicación de QKP como describen Johnson et al. [ 8 ]

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 cierta capacidad W?) es NP-completa . [ 9 ] Por lo tanto, una solución dada puede verificarse en tiempo polinomial, 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 se conoce ningún algoritmo que pueda resolverlo en tiempo polinomial.

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

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

Resolviendo

Aunque el problema de la mochila es uno de los problemas de investigación operativa (IO) más comúnmente resueltos, existen pocos algoritmos eficientes que puedan resolver problemas de mochila cuadráticos 0-1. Los algoritmos disponibles incluyen, entre otros, fuerza bruta , linealización [ 10 ] y reformulación convexa. Al igual que con otros problemas NP-difíciles , generalmente basta con encontrar una solución viable, aunque no sea necesariamente óptima. Los algoritmos heurísticos basados ​​en el algoritmo voraz y la programación dinámica pueden proporcionar una solución relativamente "buena" al problema de mochila cuadrático 0-1 de manera eficiente.

Fuerza bruta

El algoritmo de fuerza bruta para resolver este problema consiste en 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 a continuación:

// Entrada: // Ganancias (almacenadas en el array p) // Ganancias cuadráticas (almacenadas en la matriz P) // Pesos (almacenados en el array w) // Número de artículos (n) // Capacidad de la mochila (W)int max = 0 para todo subconjunto S hacer int valor , peso = 0 para i desde 0 hasta S.tamaño -1 hacer : valor = valor + p [ i ] peso = peso + w [ i ] para j desde i + 1 hasta S.tamaño -1 hacer : valor = valor + P [ i ] [ j ] si peso < = W entonces : si valor > max entonces : max = valor​​

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

Linealización

Los problemas de esta forma son difíciles de resolver directamente con solucionadores estándar, por lo que se intenta reformularlos como un programa lineal utilizando variables auxiliares y restricciones para que puedan resolverse fácilmente con 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. [ 11 ] [ 12 ] [ 13 ]

Linealización estándar

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

LP1: maximizar
∑i=1nortepagiincógnitai+∑i=1norte(∑j=1,i<jnorte(PAGij+PAGji)zij).{\displaystyle \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
zij≤incógnitai{\displaystyle z_{ij}\leq x_{i}}a pesar de(i,j),i<j{\displaystyle (i,j),i<j}
zij≤incógnitaj{\displaystyle z_{ij}\leq x_{j}}a pesar de(i,j),i<j{\displaystyle (i,j),i<j}
incógnitai+incógnitaj−1≤zij{\displaystyle x_{i}+x_{j}-1\leq z_{ij}}a pesar de(i,j),i<j{\displaystyle (i,j),i<j}
zij≥0{\displaystyle z_{ij}\geq 0}a pesar de(i,j),i<j{\displaystyle (i,j),i<j}
incógnita∈incógnita,incógnita{\displaystyle x\in X,x}binario

En la formulación LP1, hemos reemplazado el término x i x j por una variable continua z ij . Esto reformula el QKP en un problema de mochila, que luego podemos resolver de forma óptima utilizando solucionadores estándar.

Linealización de Glover

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 límites inferior y superior de∑j=1,i≠jnortePAGijincógnitaj{\displaystyle \sum _{j=1,i\neq j}^{n}P_{ij}x_{j}}, respectivamente:

LP2: maximizar
∑i=1nortepagiincógnitai+∑i=1nortezi{\displaystyle \sum _{i=1}^{n}p_{i}x_{i}+\sum _{i=1}^{n}z_{i}}
sujeto a
Liincógnitai≤zi≤Uiincógnitai{\displaystyle L_{i}x_{i}\leq z_{i}\leq U_{i}x_{i}}parai=1,…,norte{\displaystyle i=1,\ldots ,n}
∑j=1,i≠jnortePAGijincógnitaj−Ui(1−incógnitai)≤zi≤∑j=1,i≠jnortePAGijincógnitaj−Li(1−incógnitai){\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})}parai=1,…,norte{\displaystyle i=1,\ldots ,n}
incógnita∈incógnita,incógnita{\displaystyle x\in X,x}binario

En la formulación LP2, hemos reemplazado la expresión∑j=1,i≠jnortePAGijincógnitaiincógnitaj{\displaystyle \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 incluyenorte{\displaystyle n}variables auxiliares con2norte{\displaystyle 2n}restricciones mientras que la linealización estándar requiere(norte2){\displaystyle {n \choose 2}}variables auxiliares y3(norte2){\displaystyle 3{n \choose 2}}restricciones para lograr la linealidad.

Reformulación cuadrática convexa

Nótese 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∀tú,v∈S{\displaystyle \forall u,v\in S},λtú+(1−λ)v∈S{\displaystyle \lambda u+(1-\lambda )v\in S}dóndeλ∈[0,1]{\displaystyle \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 siF[λtú+(1−λ)v]≤λF(tú)+(1−λ)F(v){\displaystyle f[\lambda u+(1-\lambda )v]\leq \lambda f(u)+(1-\lambda )f(v)}Una función f es convexa siF[λtú+(1−λ)v]≥λF(tú)+(1−λ)F(v){\displaystyle f[\lambda u+(1-\lambda )v]\geq \lambda f(u)+(1-\lambda )f(v)}De manera informal, una función es cóncava si el segmento de recta que conecta dos puntos en la gráfica se encuentra por encima o sobre la gráfica, mientras que una función es convexa si se encuentra por debajo o sobre la gráfica. Por lo tanto, al reescribir la función objetivo como una función convexa equivalente, podemos reformular el programa para que sea convexo, lo cual se puede resolver utilizando paquetes de optimización.

La función objetivo se puede escribir comodoTincógnita+incógnitaTdoincógnita{\displaystyle c^{T}x+x^{T}Cx}utilizando la notación de álgebra lineal. Necesitamos hacer que P sea una matriz semidefinida positiva para poder reformular una función convexa. En este caso, modificamos la función objetivo para que seapagTincógnita+incógnitaTPAGincógnita+∑i=1norte(∑j=1,j≠inorte|PAGij|)(incógnitai2−incógnitai){\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})}aplicando resultados del álgebra lineal, donde P es una matriz diagonalmente dominante y, por lo tanto, semidefinida positiva. Esta reformulación se puede resolver utilizando un paquete cuadrático estándar de enteros mixtos comercial. [ 17 ]

Algoritmo heurístico voraz

George Dantzig [ 18 ] propuso un algoritmo de aproximación voraz para el problema de la mochila no acotado que también puede utilizarse para resolver el QKP 0-1. El algoritmo consta de dos fases: identificar una solución inicial y mejorarla.

Primero, calcule para cada elemento la contribución objetiva total que se puede lograr seleccionándolo,pagi+∑i≠jnortePAGij{\displaystyle p_{i}+\sum _{i\neq j}^{n}P_{ij}}y ordenar los artículos en orden descendente según el valor potencial por unidad de peso,(pagi+∑i≠jnortePAGij)/wi{\displaystyle (p_{i}+\sum _{i\neq j}^{n}P_{ij})/w_{i}}Luego, seleccione los elementos con la máxima relación valor-peso en la mochila hasta que no haya espacio para más, lo que forma la solución inicial. A partir de la solución inicial, la mejora se lleva a cabo mediante intercambio por pares. Para cada elemento en el conjunto de la solución, identifique los elementos que no están en el conjunto donde el intercambio resulta en una mejora del objetivo. Seleccione el par con la mejora máxima e intercámbielo. También existen posibilidades de que eliminar uno del conjunto o agregar uno al conjunto produzca la mayor contribución. Repita hasta que no haya más intercambios que mejoren. La clase de complejidad de este algoritmo esO(2norte){\displaystyle O(2^{n})}ya que, en el peor de los casos, se identificará cada combinación posible de elementos.

Quadknap

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

Heurística de programación dinámica

Si bien la programación dinámica puede generar soluciones óptimas para problemas de mochila, los enfoques de programación dinámica para QKP [ 21 ] solo pueden producir una solución de calidad relativamente buena, que puede servir como límite inferior para los objetivos óptimos. Aunque se ejecuta en tiempo pseudopolinomial, requiere mucha memoria.

Algoritmo de programación dinámica

Para simplificar, supongamos que todos los pesos son no negativos. El objetivo es maximizar el valor total sujeto a la restricción: que el peso total sea menor o igual a W. Entonces, para cadaw≤W{\displaystyle w\leq W}, definirF(metro,w){\displaystyle f(m,w)}sea ​​el valor del empaque más rentable de los primeros m artículos encontrados con un peso total de w . Es decir, sea

F(metro,w)=máximo{∑i=1metropagiincógnitai+∑i=1metro∑j=1,i≠jmetroPAGijincógnitaiincógnitaj:∑i=1metrowi=w,1≤i≤metro}.{\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\}.}

Entonces,F(metro,w){\displaystyle f(m,w)}es la solución al problema. Nótese 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 elemento e intente encontrar un mejor empaquetado considerando agregar elementos con un peso esperado de 𝑤. Si el peso del elemento a agregar excede 𝑤 , entoncesF(metro,w){\displaystyle f(m,w)}es lo mismo conF(metro−1,w){\displaystyle f(m-1,w)}Dado que el artículo tiene un peso menor en comparación con el peso deseado,F(metro,w){\displaystyle f(m,w)}es lo mismo queF(metro−1,w){\displaystyle f(m-1,w)}si la suma no aporta nada, o es la misma que la solución para una mochila con menor capacidad, específicamente una con la capacidad reducida por el peso del artículo elegido, más el valor de un artículo correcto, es decirF(metro−1,w−wmetro)+pagmetro+∑i=1metro−1PAGimetroincógnitai{\displaystyle f(m-1,w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}}. Para concluir, tenemos que

F(metro,w)={máximoF(metro−1,w),F(metro−1,w−wmetro)+pagmetro+∑i=1metro−1PAGimetroincógnitaisi wmetro≤wF(metro−1,w)de lo contrario{\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}&{\text{if }}w_{m}\leq w\\f(m-1,w)&{\text{otherwise}}\end{cases}}}

Nota sobre la clase de eficiencia: Claramente, el tiempo de ejecución de este algoritmo esO(Wnorte2){\displaystyle O(Wn^{2})}, basado en el bucle anidado y el cálculo de la ganancia del nuevo empaquetado. Esto no contradice el hecho de que el QKP sea NP-difícil, ya que W no es polinomial en la longitud de la entrada (y además no proporciona ninguna garantía de alcanzar la solución óptima).

Algoritmo de programación dinámica revisado

Tenga en cuenta que el algoritmo anterior requiereO(Wnorte2){\displaystyle O(Wn^{2})}espacio para almacenar el embalaje actual de los artículos para todos m,w , que puede no ser capaz de manejar problemas de gran tamaño. De hecho, esto se puede mejorar fácilmente eliminando el índice m deF(metro,w){\displaystyle f(m,w)}ya que todos los cálculos dependen únicamente de los resultados de la etapa anterior.

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

F(w)=máximo{∑i=1metropagiincógnitai+∑i=1metro∑j=1,i≠jmetroPAGijincógnitaiincógnitaj:∑i=1metrowi=w,metro≤norte}.{\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\right\}.}

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

F(metro)={máximoF(w),F(w−wmetro)+pagmetro+∑i=1metro−1PAGimetroincógnitaisi wmetro≤w,F(w)de lo contrario.{\displaystyle f(m)={\begin{cases}\max f(w),f(w-w_{m})+p_{m}+\sum _{i=1}^{m-1}P_{im}x_{i}&{\text{if }}w_{m}\leq w,\\f(w)&{\text{otherwise.}}\end{cases}}}

Tenga en cuenta que este algoritmo revisado todavía se ejecuta enO(Wnorte2){\displaystyle O(Wn^{2})}mientras que solo tomaO(Wnorte){\displaystyle O(Wn)}memoria en comparación con la anteriorO(Wnorte2){\displaystyle O(Wn^{2})}.

Los investigadores han estudiado el problema de la mochila cuadrática 0-1 durante décadas. Uno de los objetivos principales es encontrar algoritmos o heurísticas eficaces, especialmente aquellos con un rendimiento excepcional en la resolución de problemas del mundo real. La relación entre la versión de decisión y la versión de optimización del problema de la mochila cuadrática 0-1 no debe ignorarse al trabajar con cualquiera de ellas. Por un lado, si el problema de decisión se puede resolver en tiempo polinomial, se puede encontrar la solución óptima aplicando este algoritmo de forma iterativa. Por otro lado, si existe un algoritmo que pueda resolver el problema de optimización de manera eficiente, se puede utilizar para resolver el problema de decisión comparando la entrada con el valor óptimo.

Otro tema recurrente en la literatura es la identificación de los problemas más complejos. Los investigadores que estudian el problema 0-1 QKP suelen realizar estudios computacionales [ 22 ] para demostrar la superioridad de sus estrategias. Estos estudios también pueden utilizarse para evaluar el rendimiento de diferentes métodos de solución. En el caso del problema 0-1 QKP, estos estudios computacionales suelen basarse en datos generados aleatoriamente, introducidos por Gallo et al. Prácticamente todos los estudios computacionales del problema 0-1 QKP utilizan datos generados aleatoriamente de la siguiente manera: los pesos son enteros extraídos de una distribución uniforme en el intervalo [1, 50], y las restricciones de capacidad son enteros extraídos de una distribución uniforme entre 50 y la suma de los pesos de los ítems. Los coeficientes del objetivo, es decir, los valores, se eligen aleatoriamente en el intervalo [1, 100]. Se ha observado que la generación de instancias de esta forma produce problemas con una dificultad muy variable e impredecible. Por lo tanto, los estudios computacionales presentados en la literatura podrían ser poco fiables. Por lo tanto, algunas investigaciones tienen como objetivo desarrollar una metodología para generar instancias del problema QKP 0-1 con un nivel de dificultad predecible y consistente.

Véase también

Notas

  1. ↑ C., Witzgall (1975). "Métodos matemáticos de selección de emplazamientos para sistemas de mensajería electrónica (EMS)" . Informe interno del NBS . 76 : 18321. Bibcode : 1975STIN...7618321W . doi : 10.6028/nbs.ir.75-737 .
  2. ↑ Gallo, G.; Hammer, PL; Simeone, B. (1980). "Problemas de la mochila cuadrática". Optimización combinatoria I. Estudios de programación matemática. Vol. 12. Springer. pp. 132–149 . doi : 10.1007/bfb0120892 . ISBN   978-3-642-00801-6.
  3. ↑ Rhys, JMW (1970). "Un problema de selección de costos fijos compartidos y flujos de red". Management Science . 17 (3): 200– 207. doi : 10.1287/mnsc.17.3.200 .
  4. ↑ Helmberg, C.; Rendl, F.; Weismantel, R. (1996). "Relajaciones cuadráticas del problema de la mochila mediante planos de corte y programación semidefinida". Programación entera y optimización combinatoria . Notas de clase en informática. Vol. 1084. Springer. págs. 175–189 . doi : 10.1007/3-540-61310-2_14 . ISBN   978-3-540-61310-7.
  5. ↑ Dijkhuizen, G.; Faigle, U. (1993). "Un enfoque de plano de corte para el problema de la camarilla máxima ponderada por bordes" . European Journal of Operational Research . 69 (1): 121– 130. doi : 10.1016/0377-2217(93)90097-7 .
  6. ↑ Park, Kyungchul; Lee, Kyungsik; Park, Sungsoo (1996). "Un enfoque de formulación extendida para el problema de la camarilla máxima ponderada por bordes". European Journal of Operational Research . 95 (3): 671– 682. doi : 10.1016/0377-2217(95)00299-5 .
  7. ↑ Ferreira, CE; Martin, A.; Souza, CCDe; Weismantel, R.; Wolsey, LA (1996). "Formulaciones y desigualdades válidas para el problema de partición de grafos con capacidad de nodos". Mathematical Programming . 74 (3): 247– 266. doi : 10.1007/bf02592198 . S2CID 37819561 . 
  8. ↑ Johnson, Ellis L.; Mehrotra, Anuj; Nemhauser, George L. (1993). "Agrupamiento de corte mínimo". Programación matemática . 62 ( 1– 3): 133– 151. doi : 10.1007/bf01585164 . S2CID 39694326 . 
  9. ↑ Garey, Michael R.; Johnson, David S. (1979). Computadoras e intratabilidad: Una guía a la teoría de la completitud NP . Nueva York: Freeman and Co.
  10. ↑ Adams, Warren P.; Sherali, Hanif D. (1986). "Una linealización ajustada y un algoritmo para problemas de programación cuadrática binaria". Management Science . 32 (10): 1274– 1290. doi : 10.1287/mnsc.32.10.1274 .
  11. ↑ Adams, Warren P.; Forrester, Richard J.; Glover, Fred W. (2004). "Comparaciones y estrategias de mejora para linealizar programas cuadráticos mixtos 0-1" . Optimización discreta . 1 (2): 99– 120. doi : 10.1016/j.disopt.2004.03.006 .
  12. ↑ Adams, Warren P.; Forrester, Richard J. (2005). "Una receta simple para linealizaciones mixtas 0-1 concisas". Operations Research Letters . 33 (1): 55– 61. doi : 10.1016/j.orl.2004.05.001 .
  13. ↑ Adams, Warren P.; Forrester, Richard J. (2007). "Formas lineales de expresiones no lineales: Nuevas perspectivas sobre ideas antiguas". Operations Research Letters . 35 (4): 510– 518. doi : 10.1016/j.orl.2006.08.008 .
  14. ↑ Glover, Fred; Woolsey, Eugene (1974). "Nota técnica: conversión del problema de programación polinómica 0-1 a un programa lineal 0-1" . Operations Research . 22 (1): 180–182 . doi : 10.1287/opre.22.1.180 .
  15. ↑ Glover, Fred (1975). "Formulaciones mejoradas de programación lineal entera para problemas enteros no lineales". Management Science . 22 (4): 455– 460. doi : 10.1287/mnsc.22.4.455 . S2CID 17004334 . 
  16. ↑ Glover, Fred; Woolsey, Eugene (1973). "Reducción adicional de problemas de programación polinomial binaria a problemas de programación lineal binaria". Operations Research . 21 (1): 156– 161. doi : 10.1287/opre.21.1.156 .
  17. ↑ Bliek, Christian; Bonami, Pierre; Lodi, Andrea (2014). "Resolución de problemas de programación cuadrática con enteros mixtos con IBM-CPLEX: un informe de progreso" (PDF) . Actas del Vigésimo Sexto Simposio RAMP, Universidad Hosei, Tokio, 16-17 de octubre de 2014 .
  18. ↑ Dantzig, George B. (1957). "Problemas de extremos con variables discretas" . Operations Research . 5 (2): 266– 288. doi : 10.1016/j.disopt.2004.03.006 .
  19. ↑ Caprara, Alberto; Pisinger, David; Toth, Paolo (1999). "Solución exacta del problema de la mochila cuadrática". INFORMS Journal on Computing . 11 (2): 125– 137. CiteSeerX 10.1.1.22.2818 . doi : 10.1287/ijoc.11.2.125 . 
  20. ↑ "Quadknap" . Consultado el 3 de diciembre de 2016 .
  21. ↑ Fomeni, Franklin Djeumou; Letchford, Adam N. (2014). "Una heurística de programación dinámica para el problema de la mochila cuadrática" (PDF) . INFORMS Journal on Computing . 26 (1): 173– 182. doi : 10.1287/ijoc.2013.0555 . S2CID 15570245 . 
  22. ↑ Forrester, Richard J.; Adams, Warren P.; Hadavas, Paul T. (2009). "Formas RLT concisas de programas binarios: Un estudio computacional del problema de la mochila cuadrática". Naval Research Logistics . 57 : 1–12 . doi : 10.1002/nav.20364 . S2CID 121015443 . 
  • Códigos de David Pisinger para diferentes problemas de la mochila
  • Códigos para el problema de la mochila cuadrática. Archivado el 14 de febrero de 2015 en Wayback Machine.
Lecturas relacionadas
6 articulos
Knapsack problemKnapsack problemThe knapsack problem is the following problem in combinatorial optimization:Función de pérdidaFunción de pérdidaEn optimización matemática y teoría de decisiones , una función de pérdida o función de costo (a veces también llamada función de error) [1] es una...MochilaMochilaUna mochila —también llamada knapsack , rucksack , pack , booksack , bookbag , haversack o backsack— es, en su forma más simple sin marco, un saco ...TelecomunicacionesTelecomunicacionesEstación terrestre en la instalación de comunicaciones por satélite de Raisting Estación terrestre en Raisting , Baviera , Alemania La telecomunica...Análisis de redes de transporteAnálisis de redes de transporteUna red de transporte , o red de transporte , es una red o grafo en el espacio geográfico que describe una infraestructura que permite y restringe ...Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...