Métodos de puntos interiores para programación lineal: teoría y práctica

Abstract

Los métodos de puntos interiores han sido uno de los mayores logros de la optimización numérica de los últimos 50 años, convirtiéndose en unos buenos candidatos para resolver problemas de talla grande. En programación lineal, en vez de pivotar entre los vértices del conjunto de puntos admisibles para buscar una solución, como hace el Simplex, calculan candidatos por el interior de la región admisible. En este trabajo se han estudiado los métodos de puntos interiores primales-duales para programación lineal. En la parte teórica se han tratado con detalle algunos aspectos como el concepto del camino central y la relación con los métodos de penalización. A continuación, se han considerado dos métodos de puntos interiores: el LSPF, para el que se estudia la convergencia global, y el MPC, por ser similar a los que se implementan en MATLAB. En la parte práctica, se han comparado experimentalmente los métodos de la Optimization Toolbox de MATLAB para programación lineal. Para ello se han usado dos colecciones de tests: problemas de la librería NETLIB y problemas propios generados aleatoriamente.

Interior point methods have been one of the biggest achievements in numerical optimization over the last 50 years, turning out to be great candidates for solving large size problems. In linear programming, instead of jumping between the vertices of the feasible point set to search for a solution, like the Simplex method, interior point methods calculate candidates inside the feasible point set. The main focus of this work are primal dual interior point methods for linear programming. Firstly, some theoretical aspects such as the concept of central path and its relationship with the penalty methods have been discussed. Next, the introducction of two algorithms: the LSPF, with a study of its convergence, and the MPC, because of its similarity with the algorithms implemented on MATLAB. Finallly, the practical section focuses on the comparison between all the methods available in MATLAB’s Optimization Toolbox for linear programming. For this purpose, two colections of tests have been used: a set of problems of NETLIB’s library and a set of randomly generated problems.