@misc{CookKochSteffyetal., author = {Cook, William and Koch, Thorsten and Steffy, Daniel and Wolter, Kati}, title = {A Hybrid Branch-and-Bound Approach for Exact Rational Mixed-Integer Programming}, issn = {1438-0064}, doi = {10.1007/s12532-013-0055-6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17171}, abstract = {We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances.}, language = {en} } @article{CookKochSteffyetal., author = {Cook, William and Koch, Thorsten and Steffy, Daniel and Wolter, Kati}, title = {A hybrid branch-and-bound approach for exact rational mixed-integer programming}, series = {Mathematical Programming Computation}, volume = {5}, journal = {Mathematical Programming Computation}, number = {3}, doi = {10.1007/s12532-013-0055-6}, pages = {305 -- 344}, abstract = {We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann libraries and for a new collection of numerically difficult instances.}, language = {en} } @inproceedings{CookKochSteffyetal.2011, author = {Cook, William and Koch, Thorsten and Steffy, Daniel and Wolter, Kati}, title = {An Exact Rational Mixed-Integer Programming Solver}, series = {IPCO 2011}, volume = {6655}, booktitle = {IPCO 2011}, editor = {G{\"u}nl{\"u}k, Oktay and Woeginger, Gerhard}, doi = {10.1007/978-3-642-20807-2_9}, pages = {104 -- 116}, year = {2011}, language = {en} } @misc{CookKochSteffyetal., author = {Cook, William and Koch, Thorsten and Steffy, Daniel and Wolter, Kati}, title = {An Exact Rational Mixed-Integer Programming Solver}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12329}, number = {11-07}, abstract = {We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and the GMP arithmetic library. Computational results are presented for a suite of test instances taken from the MIPLIB and Mittelmann collections.}, language = {en} } @inproceedings{MiltenbergerRalphsSteffy, author = {Miltenberger, Matthias and Ralphs, Ted and Steffy, Daniel}, title = {Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization}, series = {Operations Research Proceedings 2017}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6}, pages = {151 -- 157}, abstract = {We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct.}, language = {en} } @misc{MiltenbergerRalphsSteffy, author = {Miltenberger, Matthias and Ralphs, Ted and Steffy, Daniel}, title = {Exploring the Numerics of Branch-and-Cut for Mixed Integer Linear Optimization}, series = {Operations Research Proceedings 2017}, journal = {Operations Research Proceedings 2017}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64645}, abstract = {We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether such predictions can be used to make better algorithmic choices. In a first step towards this goal, we discuss here the numerical behavior of an existing solver in order to determine whether our intuitive understanding of this behavior is correct.}, language = {en} } @inproceedings{GleixnerSteffyWolter2012, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Improving the Accuracy of Linear Programming Solvers with Iterative Refinement}, series = {ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation}, booktitle = {ISSAC '12. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation}, doi = {10.1145/2442829.2442858}, pages = {187 -- 194}, year = {2012}, language = {en} } @misc{GleixnerSteffyWolter, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Improving the Accuracy of Linear Programming Solvers with Iterative Refinement}, issn = {1438-0064}, doi = {10.1145/2442829.2442858}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15451}, 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 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.}, language = {en} } @article{GleixnerSteffyWolter, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Iterative Refinement for Linear Programming}, series = {INFORMS Journal on Computing}, volume = {28}, journal = {INFORMS Journal on Computing}, number = {3}, doi = {10.1287/ijoc.2016.0692}, pages = {449 -- 464}, 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.}, language = {en} } @misc{GleixnerSteffyWolter, author = {Gleixner, Ambros and Steffy, Daniel and Wolter, Kati}, title = {Iterative Refinement for Linear Programming}, issn = {1438-0064}, doi = {10.1287/ijoc.2016.0692}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55118}, 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.}, language = {en} }