Iterative Refinement for Linear Programming

References

• Althaus E, Dumitriu D (2009) Fast and accurate bounds on linear programs. Vahrenhold J, ed., Proc. 8th Internat. Sympos. Experiment. Algorithms, Lecture Notes in Computer Science, Vol. 5526 (Springer, Berlin), 40–50.Crossref, Google Scholar
• Applegate DL, Cook W, Dash S, Espinoza DG (2007a) Exact solutions to linear programming problems. Oper. Res. Lett. 35(6):693–699.Crossref, Google Scholar
• Applegate DL, Cook W, Dash S, Espinoza DG (2007b) QSopt_ex. Accessed April 19, 2016, http://www.dii.uchile.cl/~daespino/ESolver_doc/.Google Scholar
• Avis D, Fukuda K (1992) A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geometry 8(1):295–313.Crossref, Google Scholar
• Azulay D-O, Pique J-F (1998) Optimized Q-pivot for exact linear solvers. Maher M, Puget J-F, eds. Principles and Practice of Constraint Programming CP98, Lecture Notes in Computer Science, Vol. 1520 (Springer, Berlin), 55–71.Crossref, Google Scholar
• Buchheim C, Chimani M, Ebner D, Gutwenger C, Jünger M, Klau G, Mutzel P, Weiskircher R (2008) A branch-and-cut approach to the crossing number problem. Discrete Optim. 5(2):373–388.Crossref, Google Scholar
• Bulutoglu DA, Kaziska DM (2010) Improved WLP and GWP lower bounds based on exact integer programming. J. Statist. Planning Inference 140(5):1154–1161.Crossref, Google Scholar
• Burton BA, Ozlen M (2012) Computing the crosscap number of a knot using integer programming and normal surfaces. ACM Trans. Math. Software 39(1):4:1–4:18.Crossref, Google Scholar
• Chindelevitch L, Trigg J, Regev A, Berger B (2014) An exact arithmetic toolbox for a consistent and reproducible structural analysis of metabolic network models. Nature Comm. 5:Article no. 4893.Crossref, Google Scholar
• Chvátal V (1983) Linear Programming (W. H. Freeman and Company, New York).Google Scholar
• Cohn H, Jiao Y, Kumar A, Torquato S (2011) Rigidity of spherical codes. Geometry Topology 15(4):2235–2273.Crossref, Google Scholar
• Cook W, Steffy DE (2011) Solving very sparse rational systems of equations. ACM Trans. Math. Software 37(4):39:1–39:21.Crossref, Google Scholar
• Cook W, Koch T, Steffy DE, Wolter K (2011) An exact rational mixed-integer programming solver. Günlük O, Woeginger G, eds. Integer Programming and Combinatoral Optimization, Lecture Notes in Computer Science, Vol. 6655 (Springer, Berlin), 104–116.Crossref, Google Scholar
• Dantzig GB (1963) Linear Programming and Extensions (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• de Oliveira Filho FM, Vallentin F (2010) Fourier analysis, linear programming, and densities of distance avoiding sets in ℝn. J. Eur. Math. Soc. 12(6):1417–1428.Crossref, Google Scholar
• Dhiflaoui M, Funke S, Kwappik C, Mehlhorn K, Seel M, Schömer E, Schulte R, Weber D (2003) Certifying and repairing solutions to large LPs: How good are LP-solvers? Proc. 14th Ann. Sympos. Discrete Algorithms, SODA ’03 (SIAM, Philadelphia), 255–256.Google Scholar
• Edmonds J (1994) Exact pivoting. Presentation, ECCO VII, May 26–28, Milan, Italy.Google Scholar
• Edmonds J, Maurras J-F (1997) Note sur les Q-matrices d’Edmonds. RAIRO. Recherche Opérationnelle 31(2):203–209.Crossref, Google Scholar
• Espinoza DG (2006) On linear programming, integer programming and cutting planes. Unpublished doctoral dissertation, Georgia Institute of Technology, Athens, GA.Google Scholar
• Fukuda K, Prodon A (1996) Double description method revisited. Deza M, Euler R, Manoussakis I, eds. Combinatorics and Computer Science, Lecture Notes in Computer Science, Vol. 1120 (Springer, Berlin), 91–111.Crossref, Google Scholar
• Gärtner B (1999) Exact arithmetic at low cost—A case study in linear programming. Comput. Geometry 13(2):121–139.Crossref, Google Scholar
• Gleixner AM, Steffy DE, Wolter K (2012) Improving the accuracy of linear programming solvers with iterative refinement. Proc. 37th Internat. Sympos. Symbolic Algebraic Comput. (ACM, New York), 187–194.Crossref, Google Scholar
• Golub G, van Loan C (1983) Matrix Computations (Johns Hopkins University Press, Baltimore).Google Scholar
• Grötschel M, Lovasz L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer-Verlag, Berlin).Crossref, Google Scholar
• Hales TC (2005) A proof of the Kepler conjecture. Ann. Math. 162(3):1065–1185.Crossref, Google Scholar
• Held S, Cook W, Sewell E (2012) Maximum-weight stable sets and safe lower bounds for graph coloring. Math. Programming Comput. 4(4):363–381.Crossref, Google Scholar
• Hicks I, McMurray N (2007) The branchwidth of graphs and their cycle matroids. J. Combinatorial Theory Ser. B 97(5):681–692.Crossref, Google Scholar
• Jansson C (2004) Rigorous lower and upper bounds in linear programming. SIAM J. Optim. 14(3):914–935.Crossref, Google Scholar
• Khachiyan LG (1979) A polynomial algorithm in linear programming. Soviet Mathematics Doklady 20(1):191–194. [Translation].Google Scholar
• Klotz E (2014) Identification, assessment and correction of ill-conditioning and numerical instability in linear and integer programs. Newman A, Leung J, eds. TutORials in Operations Research: Bridging Data and Decisions (INFORMS, Catonsville, MD), 54–108.Link, Google Scholar
• Koch T (2004) The final NETLIB-LP results. Oper. Res. Lett. 32(2):138–142.Crossref, Google Scholar
• Ladányi L (2011) Personal communication, November 26. IBM T.J. Watson Research Center, Yorktown Heights, NY.Google Scholar
• Lerman JA, Hyduke DR, Latif H, Portnoy VA, Lewis NE, Orth JD, Schrimpe-Rutledge ACet al. (2012) In silico method for modelling metabolism and gene product expression at genome scale. Nature Comm. 3:Article no. 929.Crossref, Google Scholar
• Maes C (2013) Personal communication, September 6. Gurobi Optimization, Inc., Houston, TX.Google Scholar
• Moore RE, Kearfott RB, Cloud MJ (2009) Introduction to Interval Analysis (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• Neumaier A, Shcherbina O (2004) Safe bounds in linear and mixed-integer linear programming. Math. Programming 99(2):283–296.Crossref, Google Scholar
• Pan VY (2011) Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization. Comput. Math. Appl. 62(4):1685–1706.Crossref, Google Scholar
• Renegar J (1994) Some perturbation theory for linear programming. Math. Programming 65(1):73–91.Crossref, Google Scholar
• Saunders BD, Wood DH, Youse BS (2011) Numeric-symbolic exact rational linear system solver. Proc. 36th Internat. Sympos. Symbolic Algebraic Comput., ISSAC ’11 (ACM, New York), 305–312.Crossref, Google Scholar
• Saunders MA, Tenenblat L (2006) The zoom strategy for accelerating and warm-starting interior methods. Presentation, INFORMS Annual Meeting, Pittsburgh.Google Scholar
• Schrijver A (1986) Theory of Linear and Integer Programming (Wiley, Chichester, UK).Google Scholar
• Steffy DE, Wolter K (2013) Valid linear programming bounds for exact mixed-integer programming. INFORMS J. Comput. 25(2):271–284.Link, Google Scholar
• Ursic S, Patarra C (1983) Exact solution of systems of linear equations with iterative methods. SIAM J. Matrix Anal. Appl. 4(1):111–115.Google Scholar
• Von zur Gathen J, Gerhard J (2003) Modern Computer Algebra (Cambridge University Press, Cambridge, UK).Google Scholar
• Wan Z (2006) An algorithm to solve integer linear systems exactly using numerical methods. J. Symbolic Comput. 41(6):621–632.Crossref, Google Scholar
• Wilkinson JH (1963) Rounding Errors in Algebraic Processes (Prentice Hall, Englewood Cliffs, NJ).Google Scholar
• Wunderling R (1996) Paralleler und objektorientierter simplex-algorithmus. Unpublished doctoral thesis, Technische Universität Berlin.Google Scholar
• Yap CK (1997) Robust geometric computation. Goodman JE, O’Rourke J, eds. Handbook of Discrete and Computational Geometry (CRC Press, Boca Raton, FL), 653–668.Google Scholar