exact computation

A Computational Status Update for Exact Rational Mixed Integer Programming

  • Leon Eifler
  • Ambros Gleixner
    • Categories (Mixed) Integer Linear Programming Tags , , , , ,

    The last milestone achievement for the roundoff-error-free solution of general mixed integer programs over the rational numbers was a hybrid-precision branch-and-bound algorithm published by Cook, Koch, Steffy, and Wolter in 2013. We describe a substantial revision and extension of this framework that integrates symbolic presolving, features an exact repair step for solutions from primal heuristics, … Read more

    Iterative Refinement for Linear Programming

  • Ambros Gleixner
  • Kati Wolter
  • Daniel E. Steffy
    • Categories Linear Programming Tags , , ,

    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 … Read more