Análisis de Sensibilidad de Simplificaciones En Problemas de Optimización Lineal

Abstract

La optimización lineal es una herramienta esencial al enfrentar problemas complejos. Gracias a su capacidad para adaptarse a todo tipo de desafíos en diversos campos de aplicación, es altamente prevalente en las actividades diarias de cualquier profesión. Debido a la complejidad de los problemas de la vida real, por el número de variables y restricciones, la simplificación es clave. Además de los métodos tradicionales pre-resueltos, las operaciones de simplificación están en constante innovación para hacer estos problemas más manejables. Con este proyecto, se realiza un análisis de sensibilidad para observar la reacción de una batería de problemas a una operación de simplificación llamada esparsificación, que se llevará a cabo para diferentes niveles de significación (épsilons), desde menos hasta más simplificado. El estudio utilizará una batería de PLs del software de optimización GAMS. En primer lugar, se calculan tres índices principales, todos ellos normalizados para que sea posible hacer comparaciones entre problemas. El primero mide el valor de la función objetivo, el segundo mide la inviabilidad y el último la complejidad del problema. Los tres se calcularán para cada épsilon y, posteriormente, se obtendrán los gráficos de los tres. Una vez obtenidos los gráficos, comienza el análisis. Consiste en buscar reacciones y patrones similares en los diferentes problemas. En el análisis se identifican cuatro comportamientos principales, y solo uno de ellos muestra que la operación de simplificación merece la pena.

Linear optimization is an essential tool when facing complex problems. Thanks to its ability to adapt to all types of challenges across various fields of application, it is highly prevalent in the daily activities of any profession. Because real-life problems complexity, due to the number of variables and constraints, simplification is key. Adding to the traditional pre-solved methods, simplification operations are in constant innovation, in order to make these problems easier. With this project, a sensibility analysis is made, to see the reaction of a battery of problems to a simplification operation called sparsification, which will be done for different signification levels (epsilons) from less to more simplified. The study will use a battery of LPs from the optimization software GAMS. First of all, three main indexes are calculated, all of them normalized so it is possible making comparisons between problems. The first one measures the objective function value, the second one measures the infeasibility and the last one the complexity of the problem. The three will be calculated for every epsilon, and afterwards, the graphs for the three of them will be obtained. Once the graphs are obtained, the analysis starts. It consists of searching for similar reactions and patterns in the different problems. Four main behaviours are identified in the analysis, and only one of them shows that the simplification operation is worth it.