Este trabajo propone una nueva alternativa de generación de columnas (CG), basada en la relajación Lagrangeana con división en clusters (LagClus), para resolver el Problema de Programación Cuadrática Binaria No Restringida (PQB). La PQ es uno de los problemas clásicos de optimización no lineal, cuyo objetivo es resolver una función cuadrática mediante la elección de valores binarios adecuados para las variables de decisión. El GC propuesto trata un modelo lineal entero mixto (MILM) del PQ, que tiene restricciones representadas mediante un grafo y se particiona a través de una heurística de partición. Además de encontrar soluciones factibles, el método propuesto también presenta dos formas alternativas de obtener límites para el PQ. Se realizaron varios experimentos computacionales, utilizando instancias de difícil solución con diferentes características. El CG se compara con los métodos tradicionales de relajación de Lagrange y con otros métodos propuestos recientemente, y los resultados presentados son superiores para la mayoría de las instancias consideradas.
1. INTRODUCCIÓN
El Problema de Programación Cuadrática Binaria No Restringida (PQB) consiste en maximizar (o minimizar) una función objetivo cuadrática mediante la elección de valores adecuados para variables de decisión binarias (BEASLEY, 1998). La PQ es un problema clásico NP-Hard (BILLIONNET; ELLOUMI, 2007) en el ámbito de la optimización no lineal. Este problema aborda aplicaciones en varias áreas, como: biología molecular (PHILLIPS; ROSEN, 1994); planificación de inversiones y análisis financiero (LAUGHUNN, 1970; McBRIDE; YORMARK, 1980), y algunos problemas de tipo CAD (KRARUP; PRUZAN, 1978). Además, la PQ sigue abordando numerosos problemas modelados mediante grafos, como el de máxima camarilla, máximo conjunto independiente y otros (PARDALOS; PHILLIPS, 1990; PARDALOS; RODGERS, 1992; PARDALOS; XUE, 1994).
Los métodos exactos existentes para resolver el PQ (BILLIONNET; SUTTER, 1994; PARDALOS; RODGERS, 1990a; PARDALOS; RODGERS, 1990b) están restringidos a problemas con hasta 200 variables. Los métodos heurísticos (BEASLEY, 1998; GLOVER et al., 1998; PARDALOS; JHA, 1992) han mostrado buenos resultados para instancias con hasta 2500 variables.
Una práctica habitual para resolver el PQ es la linealización de su modelo original (ADAMS et al., 2004; GLOVER; WOOLSEY, 1974; HANSEN; MEYER, 2009), es decir, la obtención de un modelo lineal equivalente cuyas soluciones se correspondan con el modelo cuadrático original.
Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.
Artículo:
Optimización de las propiedades mecánicas y microestructuras de aleaciones AA2014/AA7075 unidas por difusión
Artículo:
Compromiso energético para un sistema suministrado por múltiples portadores de energía utilizando el algoritmo de optimización de seguimiento
Artículo:
Optimización de la programación del montaje en la industria aeronáutica
Artículo:
Establecimiento de la sostenibilidad eléctrica regional y factibilidad a través de la optimización del uso del suelo en parques eólicos
Artículo:
Desarrollo y optimización mediante diseño factorial de nanopartículas poliméricas para la administración de simvastatina
Informe, reporte:
Diagnóstico sobre la logística del comercio internacional y su incidencia en la competitividad de las exportaciones de los países miembros
Infografía:
Sistemas de calidad. Six Sigma
Manual:
Química de los taninos
Artículo:
Influencia del COVID-19 en las dinámicas de exportación, producción y consumo de carne vacuna en Colombia y el mundo: Una revisión monográfica.