Implementing cholesky factorization for interior point methods of linear programming

References

• Adler , I. , Karmarkar , N. , Resende , M.G.C. and Veiga , G. 1989 . An implementation of Karmarkar’s algorithm for linear programming . Mathematical Programming , 44 : 297 – 335 .
   Web of Science ®Google Scholar
• Altman A. Gondzio J. 1992a An efficient implementation of a higher order primal-dual interior point method for large sparse linear programs Technical Report ZTSW-l/A214/92, Systems Research Institute, Polish Academy of Sciences, Warsaw, June 1992, revised in September 1992, to appear in: Archives of Control Sciences
   Google Scholar
• Altman A. Gondzio J. HOPDM-A higher order primal-dual method for large scale linear programming (program description) European Journal of Operations Research 1992b to appear in
   Google Scholar
• Arioli , M. , Duff , I.S. and de Rijk , P.P.M. 1989 . On the augmented system approach to sparse least-squares problem . Numerische Mathematik , 55 : 667 – 684 .
   Web of Science ®Google Scholar
• Billionnet , A. and Breteau , J.F. 1989 . A comparison of three algorithms for reducing the profile of a sparse matrix . RAIRO Recherche Operationnelle , 23 : 289 – 302 .
   Web of Science ®Google Scholar
• Choi , I.C. , Monma , C.L. and Shanno , D.F. 1990 . Further development of a primal-dual interior point method . ORSA Journal on Computing , 2 : 304 – 311 .
   Google Scholar
• Dennis , J.E. and Turner , K. 1987 . Generalized conjugate directions . Linear Algebra and its Applications , 88-89 : 187 – 209 .
   Web of Science ®Google Scholar
• Duff , I.S. , Erisman , A.M. and Reid , J.K. 1989 . Direct methods for sparse matrices , New York : Oxford University Press .
   Google Scholar
• Duff , I.S. and Reid , J.K. 1982 . MA27—A set of FORTRAN subroutines for solving sparse symmetric sets of linear equations Harwell , , U K Technical Report AERE R 10533
   Google Scholar
• Eisenstat , S.C. , Gursky , M.C. , Schultz , M.H. and Sherman , A.H. 1982 . The Yale sparse matrix package I. the symmetric codes . International Journal on Numerical Methods in Engineering , 18 : 1145 – 1151 .
   Web of Science ®Google Scholar
• Forrest , J.J.H. and Tomlin , J.A. 1990 . Vector processing in simplex and interior point methods for linear programming . Annals of Operations Research , 22 : 71 – 100 .
   Google Scholar
• Gay D. M. Electronic mail distribution of linear programming test problems 1985 Mathematical Programming Society COAL Newsletter
   Google Scholar
• George , A. , Liu , J.W.H. and Ng , E.G. 1980 . User’s guide for SPARSPACK: Waterloo sparse linear equations package , Ontario , , Canada : University of Waterloo . Technical Report CS-78-30 (revised) Department of Computer Sciences
   Google Scholar
• George , A. and Liu , J.W.H. 1981 . Computer Solution of Large Sparse Positive Definite Systems , Englewood Cliffs : Prentice Hall, Inc .
   Google Scholar
• George , A. and Liu , J.W.H. 1989 . The evolution of the minimum degree ordering algorithm . SIAM Review , 31 : 1 – 19 .
   Web of Science ®Google Scholar
• Gill , P.E. , Murray , W. , Saunders , M.A. and Wright , M.H. 1984 . Sparse matrix methods in optimization . SIAM Journal on Scientific and Statistical Computing , 5 : 562 – 589 .
   Web of Science ®Google Scholar
• Gill , P.E. , Murray , W. , Saunders , M.A. , Tomlin , J.A. and Wright , M.H. 1986 . On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method . Mathematical Programming , 36 : 183 – 209 .
   Web of Science ®Google Scholar
• Goldfarb , D. and Todd , M.J. 1989 . “ Linear programming, in ” . In Optimization , Edited by: Nemhauser , G.L. , Rinnooy Kan , A.H.G. and Todd , M.J. 73 – 170 . Amsterdam : North Holland .
   Google Scholar
• Golub , G.H. and Van Loan , C.F. 1983 . Matrix Computations , Baltimore : John Hopkins University Press .
   Google Scholar
• Gondzio , J. 1992 . Splitting dense columns of constraint matrix in interior point methods for large scale linear programming . Optimization , 24 : 285 – 297 .
   Google Scholar
• Gondzio J. Tachat D. The design and application of IPMLO—a FORTRAN library for linear optimization with interior point methods University of Paris Dauphine Paris , , France 1991 Technical Report No. 108, LAMSADE, January 1992, revised in November 1992.
   Google Scholar
• Hansen , P.C. 1987 . Detection of near-singularity in Cholesky and LDL T factorizations . Journal of Computational and Applied Mathematics , 19 : 293 – 299 .
   Web of Science ®Google Scholar
• Karmarkar , N.K. and Ramakrishnan , K.G. 1991 . Computational results of an interior point algorithm for large scale linear programming . Mathematical Programming , 52 : 555 – 596 .
   Web of Science ®Google Scholar
• Markowitz , H.M. 1957 . The elimination form of the inverse and its application to linear programming . Management Science , 3 : 255 – 269 .
   Web of Science ®Google Scholar
• Munksgaard , N. 1980 . Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients . ACM Transactions on Mathematical Software , 6 ( 2 ) : 206 – 219 .
   Web of Science ®Google Scholar
• Paige , C.C. and Saunders , M.A. 1982a . LSQR: an algorithm for sparse linear equations and sparse least squares . ACM Transactions on Mathematical Software , 8 ( 2 ) : 43 – 71 .
   Web of Science ®Google Scholar
• Paige , C.C. and Saunders , M.A. 1982b . Algorithm 582 LSQR: sparse linear equations and least squares problems . ACM Transactions on Mathematical Software , 8 ( 2 ) : 195 – 209 .
   Web of Science ®Google Scholar
• Shanno , D.F. 1988 . Computing Karmarkar projections quickly . Mathematical Programming , 41 ( 2 ) : 61 – 71 .
   Google Scholar
• Tinney , W.F. and Walker , J.W. 1967 . Direct solution of sparse network equations by optimally ordered triangular factorization . Proceedings of IEEE , 55 ( 2 ) : 1801 – 1809 .
   Google Scholar
• Vanderbei , R.J. 1991 . Dense columns in interior-point methods for LP, in . Proceedings of the IMACS’ 91 World Congress on Computation and Applied Mathematics . 1991 , Dublin , Ireland.
   Google Scholar