A deficient-basis dual counterpart of Paparrizos, Samaras and Stephanides’ primal-dual simplex-type algorithmFootnote†

^†Review (November 2008) of Technical Report MA-07/01 (http://www.matap.uma.es/investigacion/tr.html), Department Applied Mathematics, University of Málaga, September 2007. Talk presented at Joint 2nd Conference on Optimization Methods & Software and 6th EUROPT Workshop on Advances in Continuous Optimization, Prague, Czech Republic, July 2007.

References

• Berkelaar , M. , Eikland , K. and Notebaert , P. 2008 . Online reference guide for lp_solve version 5.5.0.13 . Available at http://lpsolve.sourceforge.net/5.5
   Google Scholar
• Björck , Å . 1978 . Comment on the iterative refinement of least squares solutions . J. Amer. Stat. Assoc. , 73 ( 361 ) : 161 – 166 .
   Google Scholar
• Björck , Å. 1988 . A direct method for sparse least squares problems with lower and upper bounds . Numer. Math. , 54 ( 1 ) : 19 – 32 .
   Google Scholar
• Coleman , T. F. and Hulbert , L. A. 1989 . A direct active set algorithm for large sparse quadratic programs with simple bounds . Math. Prog. , 45 ( 3 ) : 373 – 406 .
   Google Scholar
• Davis , T. A. and Hager , W. W. 2005 . Row modifications of a sparse Cholesky factorization . SIAM J. Matrix Anal. Appl. , 26 ( 3 ) : 621 – 639 .
   Google Scholar
• Dolan , E. D. and Moré , J. J. 2002 . Benchmarking optimization software with performance profiles . Math. Prog. , 91 ( 2 ) : 201 – 213 .
   Web of Science ®Google Scholar
• Gill , P. E. , Murray , W. and Wright , M. H. 1991 . Numerical Linear Algebra and Optimization , Vol. 1 , Redwood City : Addison-Wesley .
   Google Scholar
• Goldfarb , D. 1994 . “ On the complexity of the simplex method ” . In Advances in Optimization and Numerical Analysis, volume 275 of Mathematics and Its Applications , Edited by: Gómez , S. and Hennart , J.-P. 25 – 38 . Dordrecht : Kluwer .
   Google Scholar
• Gonzaga , C. C. 2003 . Generation of degenerate linear programming problems . unpublished paper available at http://www.mtm.ufsc.br/~clovis/genlp.html. Federal University of Santa Catarina, April
   Google Scholar
• Higham , D. J. and Higham , N. J. 2005 . MATLAB Guide , 2 , Philadelphia : SIAM Publications .
   Google Scholar
• Li , W. , Guerrero-García , P. and Santos-Palomo , Á. 2006 . A basis-deficiency-allowing primal Phase-I algorithm using the most-obtuse-angle column rule . Comput. Math. Appl. , 51 ( 6/7 ) : 903 – 914 .
   Google Scholar
• Lougee-Heimer , R. 2005 . COIN-OR pays off . OR Today , 32 ( 5 ) : 20 – 22 .
   Google Scholar
• Mittelmann , H. D. An independent evaluation of continuous LP codes . presented at INFORMS Annual Meeting . October 2004 , Denver. with benchmark of commercial LP solvers updated in August
   Google Scholar
• Murty , K. G. 1983 . Linear Programming , New York : John Wiley and Sons .
   Google Scholar
• Pan , P.-Q. 1998 . A basis-deficiency-allowing variation of the simplex method for linear programming . Comput. Math. Appl. , 36 ( 3 ) : 33 – 53 .
   Web of Science ®Google Scholar
• Pan , P.-Q. 2005 . A revised dual projective pivot algorithm for linear programming . SIAM J. Optim. , 16 ( 1 ) : 49 – 68 .
   Google Scholar
• Pan , P.-Q. and Pan , Y.-P. 2001 . A phase-1 approach for the generalized simplex algorithm . Comput. Math. Appl. , 42 ( 10/11 ) : 1455 – 1464 .
   Google Scholar
• Pan , P.-Q. , Li , W. , Wang , Y. and Chen , T. 2002 . A Phase-I algorithm using the most-obtuse-angle rule for the basis-deficiency-allowing dual simplex method . Presented at First International Conference on Optimization Methods and Software . December 2002 , Hangzhou.
   Google Scholar
• Pan , P.-Q. , Li , W. and Wang , Y. 2004 . A Phase-I algorithm using the most-obtuse-angle rule for the basis-deficiency-allowing dual simplex method . OR Trans. (Chinese) , 8 ( 2 ) : 88 – 96 .
   Google Scholar
• Pan , P.-Q. , Li , W. and Cao , J. 2006 . Partial pricing rule simplex method with deficient basis . Numer. Math. J. Chin. Univ. (Engl. Ser.) , 15 ( 1 ) : 23 – 30 .
   Google Scholar
• Paparrizos , K. , Samaras , N. and Stephanides , G. 2003 . A new efficient primal dual simplex algorithm . Comput. Oper. Res. , 30 ( 9 ) : 1383 – 1399 .
   Google Scholar
• Santos-Palomo , Á. 2004 . The sagitta method for solving linear programs . Europ. J. Operl. Res. , 157 ( 3 ) : 527 – 539 .
   Google Scholar
• Santos-Palomo , Á. and Guerrero-García , P. 2005 . A non-simplex active-set method for linear programs in standard form . Stud. Inform. Control , 14 ( 2 ) : 79 – 84 .
   Google Scholar
• Winston , W. L. 2004 . Operations Research: Applications and Algorithms , 4 , Belmont : Duxbury Press .
   Google Scholar