Solving Large-Scale Linear Programs by Interior-Point Methods Under the MATLAB Environment

this paper, we describe our implementation of a primal-dual infeasible-interior-point algorithm for large-scale linear programming under the MATLAB environment. The resulting software is called LIPSOL -- Linear-programming Interior-Point SOLvers. LIPSOL is designed to take the advantages of MATLAB's sparse-matrix functions and external interface facilities, and of existing Fortran sparse Cholesky codes. Under the MATLAB environment, LIPSOL inherits a high degree of simplicity and versatility in comparison to its counterparts in Fortran or C language. More importantly, our extensive computational results demonstrate that LIPSOL also attains an impressive performance comparable with that of efficient Fortran or C codes in solving large-scale problems. In addition, we discuss in detail a technique for overcoming numerical instability in Cholesky factorization at the end-stage of iterations in interior-point algorithms. KEY WORDS: Linear programming, interior-point algorithms, MATLAB, LIPSOL 1 Introduction After over a decade of extraordinarily active research triggered by the seminal work of Karmarkar [5], the field of interior-point methods has finally come to maturity as far as linear programming is concerned. Not only do we have a solid theoretical foundation for interior-point methods for linear programming, but also a rather comprehensive understanding on their practical efficiency. Among many general algorithmic approaches, the most effective one in practice has proven to be the primal-dual infeasible-interior-point approach, including a number of variants and enhancements such as Mehrotra's predictor-corrector technique [13]. Recent experiments indicate that as the problem size increases, so does the frequency of interior-point methods outperforming the classic simp..