Generación de columnas con clusters para el problema de programación cuadrática binaria sin restricciones

Column generation with clusters for the unconstrained binary quadratic programming problem

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.