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 at iterations of this algorithm 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 computing approximate LP solutions and applying iterations of the simplex algorithm. We demonstrate that this algorithm is effective in practice for computing extended precision solutions and directly benefits methods for solving LPs exactly over the rational numbers.

Includes joint work with Ambros Gleixner and Kati Wolter

Tuesday, December 4, 2012

2:00– 3:00 P.M.

 372 Science and Engineering Building

(Refreshments at 3:00 PM in the kitchen area adjacent to 368 SEB)