En este artículo explico los entornos disponibles de modelamiento algebraico para problemas de programación lineal entera mixta (MILP). Explico una revisión de software disponible para resolver el problema MILP a gran escala. Finalmente comento mi experiencia resolviendo el problema de expansión de generación y transmisión de un sistema de potencia.
Actualmente para resolver problemas de programación lineal entera mixta (MILP) de gran escala se desarrolla en 2 pasos: modelar la formulación matemática y resolver con un software de optimización. El modelamiento de la formulación matemática puede ser empleando lenguajes de programación o lenguajes de modelamiento algebraico (AML).
Las ventajas de emplear el lenguaje de modelamiento algebraico son: el tiempo de implementación del modelo, la facilidad en la reformulación del problema y el rápido desarrollo de prototipos. Kallrath (2012), explica que los AML’s empleados frecuentemente son: AIMMS, AMPL, Cplex-Studio, GAMS, LINGO, LPL, Mosel, ZIMPL. Adicional a ello se tienen lenguajes no comerciales como Pyomo, FlopC++, OpenOpt, SCIP.
El software de optimización o comúnmente denominado solver matemático puede ser comercial o libre. Linderoth y Lodi (2010), realiza una revisión de software disponible para resolver problemas MILP. El autor menciona dentro de los paquetes comerciales a CPLEX, Gurobi, LINDO, Mosek y XPRESS-MP. Por otro lado, dentro de los paquetes no comerciales se tiene paquetes como BLIS, CBC, GLPK, MINTO, SCIP y SYMPHONY.
En la Tabla 1, muestro una revisión personal sobre la compatibilidad entre los lenguajes de modelamiento algebraico y los solvers. Se puede apreciar que dentro de los solver CPLEX, Gurobi y SCIP pueden ser usados por los diferentes lenguajes de modelamiento. Mientras que GAMS y LPL pueden emplean la mayor cantidad de solvers.
Meindl y Templ (2012), demuestra experimentalmente que los solver comerciales presentan un mejor rendimiento en tiempo de solución en comparación a los no comerciales. Sin embargo, no siempre garantizan la obtención de resultados para determinados problemas. En la Figura 1, se muestra la comparativa mencionada.
El precio de obtener una licencia comercial es elevada y en gran parte está sujeta a la cantidad de variables y restricciones que puede resolver. Sin embargo, también existen las licencias académicas que son asequibles e incluso gratuitas por un año. Por ejemplo, Gurobi ofrece una licencia académica gratuita por un año, solo es necesario registrarse en su página web y activar la licencia dentro de la universidad.
Es importante mencionar el servidor NEOS, el cual es un servicio ofrecido por la Universidad de Wisconsin. Este servidor NEOS pone al servicio más de 60 solvers matemáticos, entre ellos software comercial como software libre. Se puede enviar los problemas via e-mail, web o https. Por contraparte, tiene restricciones en cuanto a memoria y tiempo de solución.
Como experiencia personal, estuve resolviendo el problema de expansión de generación y transmisión de un sistema de potencia. Este problema puede ser planteado como un problema de programación lineal entera mixa, este modelamiento es parte de la tesis que estoy desarrollando. Para resolver este problema lo modele en python con la librería pyomo y lo resolvi con el solver GLPK, CBC, CPLEX y Gurobi. Proximamente, estare mostrando la comparativa en tiempo de ejecución de los software de optimización para este problema en específico.
Referencias
- Kallrath, J. (2012). Algebraic Modeling Systems: Modeling and Solving Real World Optimization Problems. Springer Science & Business Media.
- Linderoth, J. T. & Lodi, A. (2010). MILP software. Wiley encyclopedia of operations research and management science.
- Meindl, B. & Templ, M. (2012). Analysis of commercial and free and open source solvers for linear optimization problems. Eurostat and Statistics Netherlands within the project ESSnet on common tools and harmonised methodology for SDC in the ESS.
