《《1996 Solving Large-scale linear programs by interior-point methods under the MATLAB enviroment》.pdf

Copyright information to b e inserted by the Publishers Solving LargeScale Linear Programs by I nteriorPoint Metho ds Under the MATLAB Environment Yin Zhangy Department of Computational and Applied Mathematics Rice University Houston Texas USA Received August in nal form September In this pap er we describ e our implementation of a primaldual infeasibleinteriorpoint algorithm for largescale linear programming under the MATLAB environment The resulting software is called LIPSOL Linearprogramming InteriorPoint S OLvers LIPSOL is designed to take the advantages of MATLABs sparsematrix functions and external interface facilities and of existing Fortran sparse Cholesky co des Under the MATLAB environment LIPSOL inherits a high degree of simplicity and versatility in comparison to its counterparts in Fortran or C language More imp ortantly our extensive computational results demonstrate that LIPSOL also attains an impressive p erformance comparable with that of ecient Fortran or C co des in solving largescale problems In addition we discuss in detail a technique for overcoming numerical instability in Cholesky factorization at the endstage of iterations in interiorp oint algorithms KEY WORDS Linear programming interiorp oint algorithms M ATLAB LIPSOL Introduction After over a decade of extraordinarily active research triggered by the seminal work of Karmarkar the eld of interiorpoint methods has nally come to maturity as far as linear programming is concerned Not only do we have a solid theoretical foundation for interiorpoint methods for linear programming but also a rather comprehensive understanding on their practi