Implementation Of Interior Point Methods For Large Scale Linear Programming

Erling D. Andersen, Jacek Gondzio, Csaba M�� and Xiaojie Xu

In the past 10 years the interior point methods (IPM) for linear programming have gained extraordinary interest as an alternative to the sparse simplex based methods. This has initiated a fruitful competition between the two types of algorithms which has lead to very efficient implementations on both sides. The significant difference between interior point and simplex based methods is reflected not only in the theoretical background but also in the practical implementation. In this paper we give an overview of the most important characteristics of advanced implementations of interior point methods. First, we present the infeasible-primal-dual algorithm which is widely considered the most efficient general purpose IPM. Our discussion includes various algorithmic enhancements of the basic algorithm. The only shortcoming of the ``traditional'' infeasible-primal-dual algorithm is to detect a possible primal or dual infeasibility of the linear program. We discuss how this problem can be solved with the homogeneous and self-dual model.

The IPMs practical efficiency is highly dependent on the linear algebra used. Hence, we discuss this subject in great detail. Finally we cover the related topics of preprocessing and obtaining an optimal basic solution from the interior-point solution.

Technical Report 1996.3, Logilab, HEC Geneva, Section of Management Studies, University of Geneva, 102 Bd Carl-Vogt, CH-1211, Switzerland.

Contact: [email protected] (Csaba Meszaros)