Path-following methods for linear programming: a comparison with the simplex method

Abstract

This thesis introduces path-following methods for linear programming and compares them to the simplex method. This comparison involves three aspects of each method: mathematical basis of the methodology, theoretical computational complexity and computational performance in practice. Path-following methods follow the central path through the interior of the feasible region, whereas the simplex method traces around the boundary. The computational complexity of path-following methods is shown to be polynomial, while the simplex method is exponential in the worst-case. The experience of practitioners gives overwhelming evidence of the performance of the simplex method, but implementations of path-following methods can be competitive with the simplex method.