Computational experience with a modified potential reduction algorithm for linear programming

References

• Andersen , E. , Andersen , K. D. , Frenk , H. , Roos , K. , Terlaky , T. and Zhang , S. 1999 . “ The Mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm ” . In High Performance Optimization , Edited by: Andersen , E. , Andersen , K. D. , Frenk , H. , Roos , K. , Terlaky , T. and Zhang , S. 197 – 232 . Dordrecht : Kluwer Academic Press .
   Google Scholar
• Bazarra , M. , Sherali , H. and Shetty , C. 1993 . Nonlinear Programming: Theory And Algorithms , John Wiley & Sons .
   Google Scholar
• Bunch , J. and Parlett , B. 1971 . Direct methods for solving symmetric indefinite systems of linear equations . SIAM J. Numer. Anal , 8 : 639 – 655 .
   Web of Science ®Google Scholar
• Clp. COIN-OR Linear Program Solver. Available at http://www.coin-or.org/Clp/index.html
   Google Scholar
• Czyzyk , J. , Mehrotra , S. , Wagner , M. and Wright , S. 1999 . PCx: An interior-point code for linear programming . Optim. Methods Softw , 11 ( 2 ) : 397 – 430 .
   Web of Science ®Google Scholar
• Duff , I. and Reid , J. 1995 . MA47, a Fortran code for direct solution of indefinite sparse symmetric linear systems , Didcot : Central Computing Department, Rutherford Appleton Laboratory . Tech. Rep. RAL-95-001
   Google Scholar
• Fourer , R. and Mehrotra , S. 1993 . Solving symmetric indefinite systems in an interior-point method for linear programming . Math. Program , 62 : 15 – 39 .
   Web of Science ®Google Scholar
• Goldfarb , D. and Mehrotra , S. 1988 . A relaxed variant of Karmarkar's algorithm . Math. Program , 40 : 285 – 315 .
   Google Scholar
• Gondzio , J. 1996 . Multiple centrality corrections in a primal–dual method for linear programming . Comput. Optim. Appl , 6 : 137 – 156 .
   Google Scholar
• Karmarkar , N. 1984 . A new polynomial-time algorithm for linear programming . Combinatorica , 4 : 373 – 395 .
   Web of Science ®Google Scholar
• Kojima , M. , Mizuno , S. and Yoshise , A. 1991 . An O(√n L) iteration potential reduction algorithm for linear complementary problems . Math. Program , 50 : 331 – 342 .
   Web of Science ®Google Scholar
• Kojima , M. , Megiddo , N. and Mizuno , S. 1993 . A primal–dual infeasible-interior-point algorithm for linear programming . Math. Program , 61 : 263 – 280 .
   Web of Science ®Google Scholar
• Mehrotra , S. 1992 . On the implementation of a primal–dual interior point method . SIAM J. Optim , 2 : 575 – 601 .
   Web of Science ®Google Scholar
• Mehrotra , S. and Li , Z. 2005 . Convergence conditions and Krylov subspace-based corrections for primal–dual interior-point method . SIAM J. Optim , 15 : 635 – 653 .
   Web of Science ®Google Scholar
• Mizuno , S. , Todd , M. and Ye , Y. 1993 . On adaptive-step primal–dual interior-point algorithms for linear programming . Math. Oper. Res , 18 : 964 – 981 .
   Web of Science ®Google Scholar
• Mizuno , S. , Kojima , M. and Todd , M. 1995 . Infeasible-interior-point primal–dual potential-reduction algorithms for linear programming . SIAM J. Optim , 5 : 52 – 67 .
   Web of Science ®Google Scholar
• Mosek. A software for large-scale optimization problems. Available at http://www.mosek.com/
   Google Scholar
• Nesterov , Y. 1996 . Long-step strategies in interior-point primal–dual methods . Math. Program , 76 : 47 – 94 .
   Web of Science ®Google Scholar
• Netlib. A set of LP test problems in MPS format. Available at http://www.netlib.org/lp/index.html
   Google Scholar
• Ng , E. and Peyton , B. 1993 . Block sparse Cholesky algorithms on advanced uniprocessor computers . SIAM J. Sci. Comput , 14 : 1034 – 1056 .
   Web of Science ®Google Scholar
• Salahi , M. and Terlaky , T. 2007 . Adaptive large-neighborhood self-regular predictor–corrector interior-point methods for linear optimization . J. Optim. Theory Appl , 132 ( 1 ) : 143 – 160 .
   Web of Science ®Google Scholar
• Salahi , M. and Terlaky , T. 2007 . Postponing the choice of the barrier parameter in Mehrotra-type predictor–corrector algorithms . Eur. J. Oper. Res , 182 ( 2 ) : 502 – 513 .
   Web of Science ®Google Scholar
• Tanabe , K. 1988 . Centered Newton method for mathematical programming . Syst. Model. Optim , 113 : 197 – 206 .
   Google Scholar
• Todd , M. 1996 . Potential-reduction methods in mathematical programming . Math. Program , 76 : 3 – 45 .
   Web of Science ®Google Scholar
• Todd , M. and Ye , Y. 1990 . A centered projective algorithm for linear programming . Math. Oper. Res , 15 : 508 – 529 .
   Web of Science ®Google Scholar
• Tütüncü , R. 1999 . An infeasible-interior-point potential-reduction algorithm for linear programming . Math. Program , 86 : 313 – 334 .
   Web of Science ®Google Scholar
• Vanderbei , R. 1995 . Symmetric quasi-definite matrices . SIAM J. Optim , 5 : 100 – 113 .
   Web of Science ®Google Scholar
• Xu , X. , Hung , P. and Ye , Y. 1996 . A simplified homogeneous and self-dual linear programming algorithm and its implementation . Ann. Oper. Res , 62 : 151 – 171 .
   Web of Science ®Google Scholar
• Ye , Y. 1991 . An O(n 3 L) potential reduction algorithm for linear programming . Math. Program , 50( ( 1–3 ) : 239 – 258 .
   Web of Science ®Google Scholar
• Ye , Y. , Todd , M. and Mizuno , S. 1994 . An O(√n L)-iteration homogeneous and self-dual linear programming algorithm . Math. Oper. Res , 19 : 53 – 67 .
   Web of Science ®Google Scholar