Application-oriented Mixed Integer Non-Linear Programming

Programación no lineal entera mixta orientada a la aplicación

Recientemente los problemas de programación no lineal entera mixta (mixed integer non-linear programming, MINLP) han despertado un renovado interés. Esto puede explicarse por múltiples razones: (i) ha mejorado de manera considerable el desempeño de solucionadores (solvers) que manejan restricciones no lineales; (ii) la percatación de que la mayoría de las aplicaciones para el mundo real se pueden modelar mediante MINLP; (iii) lo desafiante de este tipo de problemas.

Es bien sabido que los problemas MINLP son de tipo NP-hard debido a que son la generalización de los problemas de programación lineal entera mixta. Esto significa que es muy poco probable que un algoritmo polinomial temporal exista para aquellos problemas (a menos que P = NP). Sin embargo, los MINLP son difíciles de resolver en la práctica.

El objetivo de esta investigación fue brindar un esbozo de los posibles enfoques que se pueden considerar para solucionar problemas MINLP con no convexidades, con una atención especial a problemas del mundo real. En la primera parte del documento se introduce el problema y se presentan tres casos especiales de MINLP generales y los métodos más comunes para resolverlos. Luego se describen algoritmos que abordan problemas generales de MINLP. Las partes dos y tres contienen las principales contribuciones de este estudio. En particular, la segunda parte muestra cuatro métodos distintos para solucionar diferentes clases de problemas MINLP.