Lustig, Irvin J.; Marsten, Roy E.; Shanno, David F. On implementing Mehrotra’s predictor-corrector interior-point method for linear programming. (English) Zbl 0771.90066 SIAM J. Optim. 2, No. 3, 435-449 (1992). 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. Cited in 1 ReviewCited in 95 Documents MSC: 90C05 Linear programming 90C06 Large-scale problems in mathematical programming 90-08 Computational methods for problems pertaining to operations research and mathematical programming Keywords:primal-dual interior-point algorithm Software:NETLIB LP Test Set PDFBibTeX XMLCite \textit{I. J. Lustig} et al., SIAM J. Optim. 2, No. 3, 435--449 (1992; Zbl 0771.90066) Full Text: DOI