×

On implementing Mehrotra’s predictor-corrector interior-point method for linear programming. (English) Zbl 0771.90066

Summary: S. Mehrotra [Tech. Report 90-03, Dept. of Industrial Engineering and Management Sciences, Northwestern Univ. Evanston, Illinois/USA (1990)] recently described a predictor-corrector variant of the primal- dual interior-point algorithm for linear programming. This paper describes a full implementation of this algorithm, with extensions for solving problems with free variables and problems with bounds on primal variables. Computational results on the NETLIB test set are given to show that this new method almost always improves the performance of the primal-dual algorithm and that the improvement increases dramatically as the size and complexity of the problem increases. A numerical instability in using Schur complements to remove dense columns is identifed, and a numerical remedy is given.

MSC:

90C05 Linear programming
90C06 Large-scale problems in mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI