Integración de restricciones no lineales no convexas en modelos de programación lineal

Abstract

There are systems that require the integration of non-linear functions into a linear program for their correct modeling. One way to face this problem is to express the non-linear function as a set of linear constraints. This process will be called linearization. Therefore, the linearization results in a set of linear constraints which will become part of the linear program. Being a non-linear function, and because it may or may not be convex, the restrictions obtained when linearizing it may or may not represent a problem when solving a linear program. If the non-linear function is convex the linear program can be solved with a solver without running the risk of getting wrong solutions. On the other hand, if it is a non-convex function, its linearization results in a loss of feasible region, so that when solved with a solver, a non-optimal solution can be returned. In order to avoid this problem, it could only be considered the restrictions obtained from the set of convex vertices for the solution of the linear program. However, under such approach, the risk of obtaining unfeasible solutions is one issue to be solved. This document analyzes the situations that may arise when solving a linear program to which a nonlinear non convex function has been introduced as a set of linear constraints. It presents a methodology focused on the solution of the above type of problems. To this end an algorithm for the identification of nonconvex regions as well as the vertices that delimit the border of each of these zones is proposed. Subsequently, an algorithm to assess the risk of falling into non-feasible solutions is proposed.

En muchos sistemas se requiere de la integración de restricciones no lineales como parte de un programa lineal para su correcto modelado. Una forma de enfrentar este problema es expresar la función no lineal como un conjunto de restricciones lineales. Este proceso se llamará liberalización. Por lo tanto, la liberalización da como resultado un conjunto de restricciones lineales que pasaran a formar parte del problema de programación lineal. Al tratarse de una función no lineal, existe la posibilidad de que sea o no convexa, las restricciones obtenidas por la liberalización pueden o no representar un problema al resolver con programación lineal. Si la función no lineal es convexa, el programa lineal puede ser resuelto sin correr el riesgo de obtener soluciones no factibles. Por otro lado, si se trata de una función no convexa, su liberalización resulta inevitablemente en la perdida de región factible, de modo que cuando se resuelve el problema con programación lineal, se podría devolver una solución no óptima. Para evitar esta situación, se pueden considerar solamente las restricciones obtenidas del conjunto de vértices convexos para la solución del problema. Sin embargo, bajo este enfoque, el riesgo de obtener soluciones no factibles es un problema a resolver. Esta tesis analiza las situaciones que pueden surgir al resolver un problema de programación lineal en el que se ha introducido una función no lineal no convexa como un conjunto de restricciones lineales y presenta una metodología diseñada para la solución de este tipo de problemas. Con este fin, se propone un algoritmo para la identificación de regiones no convexas, así como los vértices que delimitan la frontera de cada una de estas zonas. Posteriormente, se propone un algoritmo para identificar posibles soluciones no factibles causadas por la integración de la restricción no convexa.