<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1545</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-05-08</completedDate>
    <publishedDate>2012-05-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Improving the Accuracy of Linear Programming Solvers with Iterative Refinement</title>
    <abstract language="eng">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.&#13;
&#13;
We demonstrate that this algorithm is effective in practice for computing extended precision solutions and that this leads to direct improvement of the best known methods for solving LPs exactly over the rational numbers.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15451</identifier>
    <identifier type="doi">10.1145/2442829.2442858</identifier>
    <enrichment key="SourceTitle">Appeared in: ISSAC '12 Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation pp. 187-194</enrichment>
    <author>Ambros Gleixner</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Daniel Steffy</author>
    <author>Kati Wolter</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-19</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Linear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Iterative refinement</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Exact linear programming</value>
    </subject>
    <collection role="ccs" number="G.4">MATHEMATICAL SOFTWARE</collection>
    <collection role="ccs" number="D.2.8">Metrics (D.4.8)</collection>
    <collection role="ccs" number="I.1.2">Algorithms (F.2.1-2)</collection>
    <collection role="msc" number="90C05">Linear programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="SPP1307-ExactIP">SPP1307-ExactIP</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1545/ZR_12-19.pdf</file>
  </doc>
</export-example>
