A pivoting algorithm for linear programming with linear complementarity constraints

References

• Anitescu , M. 2005 . On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints . SIAM J. Optim. , 15 : 1203 – 1236 .
   Web of Science ®Google Scholar
• Anitescu , M. , Tseng , P. and Wright , S. J. 2007 . Elastic-mode algorithms for mathematical programs with equilibrium constraints . Math. Program. , 110 : 337 – 371 .
   Web of Science ®Google Scholar
• Audet , C. , Hansen , P. , Jaumard , B. and Savard , G. 1997 . Links between linear bilevel and mixed 0-1 programming problems . J. Optim. Theory Appl. , 93 : 273 – 300 .
   Web of Science ®Google Scholar
• Audet , C. , Savard , S. and Zghal , W. 2007 . New branch-and-cut algorithm for bilevel linear programming . J. Optim. Theory Appl. , 134 : 353 – 370 .
   Web of Science ®Google Scholar
• Bard , J. F. and Moore , J. T. 1990 . A branch and bound algorithm for the bilevel programming problem . SIAM J. Sci. Comput. , 11 ( 2 ) : 281 – 292 .
   Web of Science ®Google Scholar
• Bartels , R. H. and Golub , G. H. 1969 . Algorithm 350: Simplex method procedure employing LU decomposition . Commun. ACM , 12 : 275 – 281 .
   Web of Science ®Google Scholar
• Bartels , R. H. and Golub , G. H. 1969 . The simplex method of linear programming using LU decomposition . Commun. ACM , 12 : 266 – 268 .
   Web of Science ®Google Scholar
• Benson , H. , Sen , A. , Shanno , D. F. and Vanderbei , R. V.D. 2006 . Interior-point algorithms, penalty methods and equilibrium problems . Comput. Optim. Appl. , 34 ( 2 ) : 155 – 182 .
   Web of Science ®Google Scholar
• Campêlo , M. and Scheimberg , S. 2000 . A note on a modified simplex approach for solving bilevel linear programming problems . European J. Oper. Res. , 126 : 454 – 458 .
   Google Scholar
• Chvátal , V. 1983 . “ Linear Programming ” . New York and San Francisco : W.H. Freeman & Company .
   Google Scholar
• Dolan , E. D. and Moré , J. J. 2002 . Benchmarking optimization software with performance profiles . Math. Program. Ser. A , 91 : 201 – 213 .
   Web of Science ®Google Scholar
• Dolan , E. D. , Moré , J. J. and Munson , T. 2006 . Optimality measures for performance profiles . SIAM J. Optim. , 16 ( 3 ) : 891 – 909 .
   Web of Science ®Google Scholar
• Facchinei , F. , Jiang , H. and Qi , L. 1999 . A smoothing method for mathematical programs with equilibrium constraints . Math. Program. , 85 : 107 – 134 .
   Web of Science ®Google Scholar
• Ferris , M. C. , Fourer , R. and Gay , D. M. 1999 . Expressing complementarity problems in an algebraic modeling language and communicating them to solvers . SIAM J. Optim. , 9 : 991 – 1009 .
   Google Scholar
• Fletcher , R. and Leyffer , S. 2004 . Solving mathematical program with complementarity constraints as nonlinear programs . Optim. Methods Softw. , 19 ( 1 ) : 15 – 40 .
   Web of Science ®Google Scholar
• Fletcher , R. and Matthews , S. P.J. 1984 . Stable modification of explicit LU factors for simplex updates . Math. Program. , 30 ( 3 ) : 267 – 284 .
   Google Scholar
• Fletcher , R. , Leyffer , S. , Ralph , D. and Scholtes , S. 2006 . Local convergence of SQP methods for mathematical programs with equilibrium constraints . SIAM J. Optim. , 17 ( 1 ) : 259 – 286 .
   Web of Science ®Google Scholar
• Fourer , R. , Gay , D. M. and Kernighan , B. W. 2002 . AMPL: A Modeling Language for Mathematical Programming , 2 , Pacific Grove , CA : Duxbury Press .
   Google Scholar
• Fukushima , M. and Tseng , P. 2002 . An implementable active-set algorithm for computing a B-stationary point for a mathematical program with linear complementarity constraints . SIAM J. Optim. , 12 : 724 – 739 .
   Web of Science ®Google Scholar
• Gill , P. E. , Murray , W. and Wright , M. H. 1990 . Numerical Linear Algebra and Optimization , Redwood City , CA : Addison Wesley Publishing Company .
   Google Scholar
• Goldfarb , D. and Reid , J. K. 1977 . A practical steepest-edge simplex algorithm . Math. Program. , 12 : 361 – 371 .
   Google Scholar
• Hansen , P. , Jaumard , B. and Savard , G. 1992 . New branch-and-bound rules for linear bilevel programming . SIAM J. Sci. Stat. Comput. , 13 ( 5 ) : 1194 – 1217 .
   Web of Science ®Google Scholar
• Hoheisel , T. and Kanzow , C. 2009 . On the Abadie and Guignard constraint qualifications for mathematical programmes with vanishing constraints . Optimization , 58 : 431 – 448 .
   Web of Science ®Google Scholar
• Hu , X. M. and Ralph , D. 2004 . Convergence of a penalty method for mathematical programming with complementarity constraints . J. Optim. Theory Appl. , 123 : 365 – 390 .
   Web of Science ®Google Scholar
• Hu , J. , Mitchell , J. E. , Pang , J.-S. , Bennet , K. P. and Kunapuli , G. 2008 . On the global solution of linear programs with linear complementarity constraints . SIAM J. Optim. , 19 : 445 – 471 .
   Google Scholar
• Hu , J. , Mitchell , J. E. , Pang , J.-S. , Bennett , K. P. and Kunapuli , G. 2008 . On the global solution of linear programs with linear complementarity constraints . SIAM J. Optim. , 19 ( 1 ) : 445 – 471 .
   Google Scholar
• Ibaraki , T. 1971 . Complementary programming . Oper. Res. , 19 : 1523 – 1529 .
   Google Scholar
• Ibaraki , T. 1973 . The use of cuts in complementary programming . Oper. Res. , 21 : 353 – 359 .
   Google Scholar
• Jiang , H. and Ralph , D. 2000 . Smooth SQP methods for mathematical programs with nonlinear complementarity constraints . SIAM J. Optim. , 10 : 779 – 808 .
   Web of Science ®Google Scholar
• Jiang , H. and Ralph , D. 2004 . Extension of quasi-Newton methods to mathematical programs with complementarity constraints . Comput. Optim. Appl. , 123 : 365 – 390 .
   Google Scholar
• Júdice , J. J. and Faustino , A. M. 1992 . A sequential LCP method for bilevel linear programming . Ann. Oper. Res. , 34 ( 1–4 ) : 89 – 106 .
   Google Scholar
• Júdice , J. J. , Sherali , H. D. , Ribeiro , I. M. and Faustino , A. M. 2006 . A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints . J. Global Optim. , 36 ( 1 ) : 89 – 114 .
   Google Scholar
• Júdice , J. J. , Sherali , H. D. , Ribeiro , I. M. and Faustino , A. M. 2007 . Complementarity active-set algorithm for mathematical programming problems with equilibrium constraints . J. Optim. Theory Appl. , 134 ( 3 ) : 467 – 481 .
   Google Scholar
• Leyffer , S. 2000 . MacMPEC: AMPL collection of MPECs Available at www.mcs.anl.gov/~leyffer/MacMPEC/
   Google Scholar
• Leyffer , S. 2005 . The penalty interior point method fails to converge . Optim. Methods Softw. , 20 : 559 – 568 .
   Web of Science ®Google Scholar
• Leyffer , S. 2006 . “ Complementarity constraints as nonlinear equations: Theory and numerical experience ” . In Optimization with Multivalued Mappings , Edited by: Dempe , S. and Kalashnikov , V. 169 – 208 . New York : Springer .
   Google Scholar
• S. Leyffer and T. Munson, A globally convergent filter method for MPECs, preprint (2007), ANL/MCS-P1457-0907, Argonne National Laboratory, Mathematics and Computer Science Division
   Google Scholar
• Leyffer , S. , Lopéz-Calva , G. and Nocedal , J. 2006 . Interior methods for mathematical programs with complementarity constraints . SIAM J. Optim. , 17 ( 1 ) : 52 – 77 .
   Web of Science ®Google Scholar
• Önal , H. 1993 . A modified simplex approach for solving bilevel linear programming problems . European J. Oper. Res. , 67 : 126 – 135 .
   Web of Science ®Google Scholar
• Pang , J.-S. and Fukushima , M. 1999 . Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints . Comput. Optim. Appl. , 131–3 : 111 – 136 .
   Google Scholar
• Scheel , H. and Scholtes , S. 2000 . Mathematical program with complementarity constraints: Stationarity, optimality and sensitivity . Math. Oper. Res. , 25 : 1 – 22 .
   Web of Science ®Google Scholar
• Scholtes , S. 2001 . Convergence properties of a regularization scheme for mathematical programs with complementarity constraints . SIAM J. Optim. , 11 : 918 – 936 .
   Web of Science ®Google Scholar
• Stange , P. , Griewank , A. and Bollhöfer , M. 2007 . On the efficient update of rectangular LU-factorizations subject to low rank modifications . Electron. Trans. Numer. Anal. , 26 : 161 – 177 .
   Google Scholar
• Ye , J. J. 1999 . Optimality conditions for optimization problems with complementarity constraints . SIAM J. Optim. , 9 ( 2 ) : 374 – 387 .
   Web of Science ®Google Scholar
• Ye , J. J. 2005 . Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints . J. Math. Anal. Appl. , 307 : 350 – 369 .
   Web of Science ®Google Scholar