Interior point methods for linear programming

Abstract

The introduction of interior point methods came about as an alternative linear programming solver to Dantzig's Simplex algorithm. In this dissertation, we will study a series of methods with a polynomial-time order which offer superior theoretical properties and improved efficiency features when compared to an exponential-time order method such as the Simplex algorithm. This class of methods from the optimization field solves linear programs by searching for an optimal point through the interior of the feasible region, as opposed to the Simplex' s approach of searching along the boundaries. We will study interior point methods such as the Ellipsoid algorithm, Karmarkar's Projective algorithm and the Primal-Dual Path-Following algorithm. This dissertation addresses the complexity issues of such algorithms, puts them into practice using software such as MATLAB and Mathematica, compares their performance with the Simplex's performance and aims to conclude which algorithm (or type of algorithm) is the most efficient solver for linear programs.