Permutations in the Factorization of Simplex Bases

References

• Bartels RH, Golub GH (1969) The simplex method of linear programming using LU decomposition. Comm. ACM 12(5):266–268.Crossref, Google Scholar
• Bixby RE (2009) Solving LPs in practice. Communication at the combinatorial optimization at work summer school. Accessed January 18, 2019, http://co-at-work.zib.de/berlin2009/downloads/2009-09-24/2009-09-24-1100-BB-Linear-Programming-2.pdf.Google Scholar
• Chvátal V (1983) Linear Programming (W. H. Freeman and Company, New York).Google Scholar
• Forrest J, Tomlin J (1972) Updated triangular factors of the basis to maintain sparsity in the product form simplex method. Math. Programming 2(1):263–278.Crossref, Google Scholar
• Forrest J, de la Nuez D, Lougee-Heimer R (2004) Coin-Clp user guide. Accessed January 18, 2019, http://www.coin-or.org/Clp/userguide/index.html.Google Scholar
• Forrest JJ, Goldfarb D (1992) Steepest-edge simplex algorithms for linear programming. Math. Programming 57(1):341–374.Crossref, Google Scholar
• Fourer R (1994) Notes on the dual simplex method. Draft report. Accessed January 18, 2019, http://users.iems.northwestern.edu/∼4er/WRITINGS/dual.pdf.Google Scholar
• Gurobi Optimization, Inc. (2014) Gurobi optimizer reference manual. Accessed January 18, 2019, http://www.gurobi.com.Google Scholar
• Hall J (1991) Sparse matrix algebra for active set methods in linear programming. PhD thesis, University of Dundee Department of Mathematics and Computer Science, Dundee, United Kingdom.Google Scholar
• Huangfu Q (2013) High performance simplex solver. PhD thesis, University of Edinburgh, Edinburgh, United Kingdom.Google Scholar
• Huangfu Q, Hall J (2014) Novel update techniques for the revised simplex method. Comput. Optim. Appl. 60(3):587–608.Crossref, Google Scholar
• IBM (2014) ILOG CPLEX optimizer. Accessed January 18, 2019, https://www.ibm.com/analytics/cplex-optimizer.Google Scholar
• Kirillova F, Gabasov R, Kostyukova O (1979) A method of solving general linear programming problems. Doklady BSSR 23(3):197–200.Google Scholar
• Koberstein A (2005) The dual simplex method, techniques for a fast and stable implementation. PhD thesis, Fakultät für Wirtschaftswissenschaften der Universität Paderborn, Paderborn, Germany.Google Scholar
• Koberstein A (2008) Progress in the dual simplex algorithm for solving large scale lp problems: Techniques for a fast and stable implementation. Comput. Optim. Appl. 41(2):185–204.Crossref, Google Scholar
• Koch T, Achterberg T, Andersen E, Bastert O, Berthold T, Bixby RE, Danna E, et al.. (2011) MIPLIB 2010. Math. Programming Comput. 3(2):103–163.Crossref, Google Scholar
• Luce R, Duintjer Tebbens J, Nabben LR, Grötschel M, Koch T, Schenk O (2009) On the factorization of simplex basis matrices. ZIB-Report 09-24 (July 2009). Accessed January 18, 2019, https://opus4.kobv.de/opus4-zib/files/1139/ZR_09_24.pdf.Google Scholar
• Maros I (2003) Computational Techniques of the Simplex Method (Kluwer Academic Publishers, Norwell, MA).Crossref, Google Scholar
• Mittelmann H (2016) Benchmarks for optimization software. Accessed January 18, 2019, http://plato.asu.edu/bench.html.Google Scholar
• Orchard-Hayes W (1968) Advanced Linear-Programming Computing Techniques (McGraw-Hill, New York).Google Scholar
• Reid J (1982) A sparsity-exploiting variant of the Bartels—Golub decomposition for linear programming bases. Math. Programming 24(1):55–69.Crossref, Google Scholar
• Saunders M (1976a) The complexity of LU updating in the simplex method. Anderssen RS, Brent RP, eds. The Complexity of Computational Problem Solving (University of Queensland Press, St. Lucia, QLD, Australia), 214–230.Google Scholar
• Saunders M (1976b) A fast, stable implementation of the simplex method using Bartels-Golub updating. Bunch JR, Rose DJ, eds. Sparse Matrix Computations (Academic Press, New York), 213–226.Crossref, Google Scholar
• Suhl LM, Suhl UH (1993) A fast LU update for linear programming. Ann. Oper. Res. 43(1):33–47.Crossref, Google Scholar
• Suhl UH, Suhl LM (1990) Computing sparse LU factorizations for large-scale linear programming bases. ORSA J. Comput. 2(4):325–335.Link, Google Scholar