×

zbMATH — the first resource for mathematics

Implementation of interior-point methods for large scale linear programs. (English) Zbl 0874.90127
Terlaky, Tamás (ed.), Interior point methods of mathematical programming. Dordrecht: Kluwer Academic Publishers. Appl. Optim. 5, 189-252 (1996).
Summary: 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 led 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.
For the entire collection see [Zbl 0866.00024].

MSC:
90C05 Linear programming
90C06 Large-scale problems in mathematical programming
Software:
MOPS
PDF BibTeX Cite