Optimization Online


Iterative Refinement for Linear Programming

Ambros M. Gleixner(gleixner***at***zib.de)
Daniel E. Steffy(steffy***at***oakland.edu)
Kati Wolter(support***at***mosek.com)

Abstract: 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.

Keywords: Linear programming, exact computation, iterative refinement, rational arithmetic

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: ZIB-Report 15-15, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustraße 7, 14195 Berlin, ISSN 1438-0064

Download: [PDF]

Entry Submitted: 06/06/2015
Entry Accepted: 06/06/2015
Entry Last Modified: 06/06/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society