×

zbMATH — the first resource for mathematics

Solving large-scale linear programs by interior-point methods under the Matlab environment. (English) Zbl 0916.90208
Summary: 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.

MSC:
90C05 Linear programming
90C06 Large-scale problems in mathematical programming
Software:
LIPSOL; Matlab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen E. D., Implementation of interior-point methods for large-scale linear programming (1996) · Zbl 0874.90127
[2] Choi I. C., ORSA J. on Computing. 2 pp 304– · Zbl 0757.90051 · doi:10.1287/ijoc.2.4.304
[3] Gay D. M., Mathematical Programming Society COAL Newsletter 13 pp 10– (1985)
[4] Gondzio J., Computational Optimization and Applications 13 (1985)
[5] DOI: 10.1007/BF02579150 · Zbl 0557.90065 · doi:10.1007/BF02579150
[6] Kojima M., Progress in mathematical programming, interior-point and related methods pp 29– (1989)
[7] DOI: 10.1007/BF01582151 · Zbl 0808.90093 · doi:10.1007/BF01582151
[8] DOI: 10.1137/0614019 · Zbl 0765.65034 · doi:10.1137/0614019
[9] DOI: 10.1016/0024-3795(91)90275-2 · Zbl 0731.65049 · doi:10.1016/0024-3795(91)90275-2
[10] DOI: 10.1137/0802022 · Zbl 0771.90066 · doi:10.1137/0802022
[11] Lustig I. J., ORSA J. on Computing 6 pp 1– (1994) · Zbl 0798.90100 · doi:10.1287/ijoc.6.1.1
[12] Lustig, I. J. Barrier algorithms for linear programming. Workshop on Computational Linear and Integer Programming, Fifth INFORMS Computer Science Technical Section Conference. pp.7–10. Dallas, USA
[13] DOI: 10.1137/0802028 · Zbl 0773.90047 · doi:10.1137/0802028
[14] DOI: 10.1287/moor.18.4.964 · Zbl 0810.90091 · doi:10.1287/moor.18.4.964
[15] Nazareth L. L., Computer Solution of Linear Programs (1987) · Zbl 0643.90042
[16] Ortega J. M., Iterative Solution of Nonlinear Equations in Several Variables (1970) · Zbl 0241.65046
[17] DOI: 10.1137/0806004 · Zbl 0846.65024 · doi:10.1137/0806004
[18] Xu X., A simplified homogeneous and self-dual linear programming algorithm (1993)
[19] DOI: 10.1137/0804012 · Zbl 0803.90092 · doi:10.1137/0804012
[20] Zhang, Y. 1995. ”User’s Guide to LIPSOL”. Baltimore, MD: Dept. of Mathematics and Statistics, University of Maryland Baltimore County. Technical Report TR95-19
[21] DOI: 10.1007/BF01585769 · Zbl 0837.90087 · doi:10.1007/BF01585769
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.