On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear Programming

TLDR

Mehrotra’s 1990 report introduced a predictor–corrector variant of the primal–dual interior‑point algorithm for linear programming. This paper presents a complete implementation of Mehrotra’s algorithm, extending it to handle free variables and primal bounds. The authors implement the predictor–corrector method, augmenting it with routines for free variables and bound handling. Computational experiments on the NETLIB test set demonstrate that the extended method consistently outperforms the standard primal–dual algorithm, with larger gains for bigger, more complex problems, and a numerical remedy is provided for instability arising from Schur complement column removal.

Abstract

Mehrotra [Tech. Report 90-03, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 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 identified, and a numerical remedy is given.