Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Iterative Refinement for Linear Programming

Please always quote using this URN: urn:nbn:de:0297-zib-55118
  • We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Ambros GleixnerORCiD, Daniel SteffyORCiD, Kati Wolter
Document Type:ZIB-Report
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C05 Linear programming
Date of first Publication:2015/05/28
Series (Serial Number):ZIB-Report (15-15)
ISSN:1438-0064
Published in:INFORMS Journal on Computing
Preprint:urn:nbn:de:0297-zib-55118
DOI:https://doi.org/10.1287/ijoc.2016.0692
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.