An affine-scaling pivot algorithm for linear programming

References

• Adler , I , Karmarkar , N , Resende , M and Veiga , G . 1989 . Data structure and programming techniques for the implementation of Karmarkar's algorithm . ORSA J. Comput. , 1 : 84 – 106 .
   Google Scholar
• Adler , I , Resende , M , Veiga , G and Karmarkar , N . 1989 . An implementation of Karmarkar's algorithm for linear programming . Math. Progr. , 44 : 297 – 335 .
   Web of Science ®Google Scholar
• Barnes , ER . 1986 . A variation of Karmarkars's algorithm for solving linear programming problems . Math. Progr. , 36 : 174 – 182 .
   Web of Science ®Google Scholar
• Bartels , RH and Golub , GH . 1969 . The simplex method of linear programming using LU decomposition . Commun. ACM , 12 : 275 – 278 .
   Web of Science ®Google Scholar
• Beale , EML . 1955 . An alternative method for linear programming, In Cycling in the dual simplex algorithm . Naval Res. Log. Quart. , 2 : 269 – 275 .
   Google Scholar
• Bland , RG . 1977 . New finite pivoting rules for the simplex method . Math. Oper. Res. , 2 : 103 – 107 .
   Google Scholar
• Cavalier , TM and Soyster , AL . 1985 . Some computational experience and a modification of the karmarkar algorithm , The Pennsylvania State University : ISME Working paper . pp. 85–105
   Google Scholar
• Dantzig , GB . 1948 . Programming in a Linear Structure, Comptroller , Washington, DC : USAF .
   Google Scholar
• Dantzig , GB . 1949 . Programming of independent activities. Part II Mathematical model . Econometrica , 17 : 200 – 211 .
   Web of Science ®Google Scholar
• Dantzig , GB . Computational algorithm of the revised simplex method, Report RM 1266, The Rand Corporation, Santa Monica, CA, 1953
   Google Scholar
• Dantzig , GB . 1954 . The product form for the inverse in the simplex method . Math. Tables Other Aids Comput. , 8 : 64 – 67 .
   Google Scholar
• Dikin , II . 1967 . Iterative solution of problems of linear and quadratic programming . Sov. Math. Dokl. , 8 : 674 – 675 .
   Google Scholar
• Dikin , II . 1974 . On the convergence of an iterative process . Upravlyaemye Sist. , 12 : 54 – 60 . (in Russian)
   Google Scholar
• Forrest , JJH and Goldfarb , D . 1992 . Steepest-edge simplex algorithms for linear programming . Math. Progr. , 57 : 341 – 374 .
   Web of Science ®Google Scholar
• Forrest , JJH and Tomlin , JA . 1972 . Updated triangular factors of the basis to maintain sparsity in the product form simplex method . Math. Progr. , 2 : 263 – 278 .
   Google Scholar
• Gay , DM . 1985 . Electronic mail distribution of linear programming test problems . Math. Progr. Soc. COAL Newsletter , 13 : 10 – 12 .
   Google Scholar
• Gill , PE , Golub , GH , Murray , W and Saunders , MA . 1974 . Methods for modifying matrix factorization . Math. Comp. , 28 : 505 – 538 .
   Web of Science ®Google Scholar
• Gill , PE , Murray , W , Saunders , MA and Wright , MH . 1989 . A practical anticycling procedure for linearly constrained optimization . Math. Progr. , 45 : 437 – 474 .
   Web of Science ®Google Scholar
• Golub , GH and Van Loan , CF . 1983 . Matrix Computations , Baltimore : The Johns Hopkins University Press .
   Google Scholar
• Gonzaga , CC . Convergence of the large step primal affine-scaling algorithm, for primal non-degenerate linear programs, Technical Report, Department of Systems Engineering and Computer Sciences, COPPE-Federal University of Rio de Janeiro, Brazil, 1990
   Google Scholar
• Greenberg , H-J . 1978 . “ Pivot selection tactics ” . In Design and Implementation of Optimization Software , Edited by: Greenberg , HJ . 109 – 143 . The Netherlands : Sijthoff and Noordhoff .
   Google Scholar
• Hager , WW . 1998 . “ The LP dual active set algorithm ” . In High-Performance Algorithms and Sofware in Nonliear Optimization , Edited by: De Leone , R , Murli , A , Pardalos , PM and Toraldo , G . 243 – 254 . Dordrecht : Kluwer .
   Google Scholar
• Hager , WW . 2002 . The LP dual active set algorithm and its application to linear programming . Comput. Optim. Appl. , 21 : 263 – 275 .
   Web of Science ®Google Scholar
• Harris , JPM . 1975 . Pivot selection methods of the Devex LP code . Math. Progr. Study , 4 : 30 – 57 .
   Google Scholar
• Jeroslow , RG . 1973 . The simplex algorithm with the pivot rule of maximizing criterion improvement . Discr. Math. , 4 : 367 – 377 .
   Google Scholar
• Karmarkar , N . 1984 . A new polynomial time algorithm for linear programming . Combinatorica , 4 : 373 – 395 .
   Web of Science ®Google Scholar
• Karmarkar , N and Ramakrishnan , K . Further developments in the new polynomial-time algorithm for linear programming. Talk given at ORSA/TIMES April National Meeting, Boston, 1985
   Google Scholar
• Khachiyan , LG . 1979 . A polynomial algorithm in linear programming . Dokl. Akad. Nauk USSR , 244 : 1093 – 1096 . (in Russian). (English translation: Sov. Math. Dokl. 20 (1979), pp. 191–194.)
   Google Scholar
• Klee , V and Minty , GJ . 1972 . “ How good is the simplex algorithm? ” . In Inequalities, III , Edited by: Shisha , O . 159 – 175 . New York : Academic Press .
   Google Scholar
• Kortanek , KO and Shi , M . 1987 . Convergence results and numerical experiments on a linear programming hybrid algorithm . Eur. J. Oper. Res. , 32 : 47 – 61 .
   Web of Science ®Google Scholar
• Lemke , CE . 1954 . The dual method of solving the linear programming problems . Naval Res. Log. Quart. , 1 : 36 – 47 .
   Google Scholar
• Pan , P-Q . 1990 . Practical finite pivoting rules for the simplex method . OR Spektrum , 12 : 219 – 225 .
   Google Scholar
• Pan , P-Q . 1991 . A simplex-like method with bisection for linear programming . Optimization , 22 : 717 – 743 .
   Google Scholar
• Pan , P-Q . 1996 . A modified bisection simplex method for linear programming . J. Comput. Math. , 14 : 249 – 255 .
   Web of Science ®Google Scholar
• Pan , P-Q . 1997 . The most-obtuse-angle row pivot rule for achieving dual feasibility: A computational study . Eur. J. Oper. Res. , 101 : 167 – 176 .
   Web of Science ®Google Scholar
• Pan , P-Q . 1998 . A dual projective simplex method for linear programming . Comput. Math. Appl. , 35 : 119 – 135 .
   Web of Science ®Google Scholar
• Pan , P-Q . 1998 . A basis-deficiency-allowing variation of the simplex method . Comput. Math. Appl. , 36 : 33 – 53 .
   Web of Science ®Google Scholar
• Pan , P-Q . 1999 . A projective simplex method for linear programming . Linear Algebra Appl. , 292 : 99 – 125 .
   Web of Science ®Google Scholar
• Pan , P-Q . 2000 . A projective simplex algorithm using LU factorization . Comput. Math. Appl. , 39 : 187 – 208 .
   Web of Science ®Google Scholar
• Pan , P-Q . 2004 . A dual projective pivot algorithm for linear programming . Comput. Optim. Appl. , 29 : 333 – 344 .
   Web of Science ®Google Scholar
• Pan , P-Q . 2005 . A revised dual projective pivot algorithm for linear programming . SIAM J. Optim. , 16 : 49 – 68 .
   Web of Science ®Google Scholar
• Tsuchiya , T and Muramatsu , M . 1995 . Global convergence of a long-step affine scaling algorithm for degenerate linear programming problems . SIAM J. Optim. , 5 : 525 – 551 .
   Web of Science ®Google Scholar
• Vanderbei , RJ , Meketon , MS and Freedman , BA . 1986 . A modification of Karmarkar's linear programming algorithm . Algorithmica , 1 : 395 – 407 .
   Web of Science ®Google Scholar
• Zionts , S . The criss-cross method for solving linear programming problems, Mgmt. Sci. 15 (1969), pp. 420–445
   Google Scholar
• Terlaky , T . A covergent criss-cross method, Math. Oper. und Stat. Ser. Optim. 16 (1985), pp. 683–690
   Google Scholar