@misc{SteffyWolter, author = {Steffy, Daniel and Wolter, Kati}, title = {Valid Linear Programming Bounds for Exact Mixed-Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12332}, number = {11-08}, abstract = {Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be exactly feasible, giving a valid bound. Solutions are repaired by performing a projection and a shift to ensure all constraints are satisfied; bound computations are accelerated by reusing structural information through the branch-and-bound tree. We demonstrate this method to be widely applicable and faster than solving a sequence of exact LPs. Several variations of the algorithm are described and computationally evaluated in an exact branch-and-bound algorithm within the mixed-integer programming framework SCIP.}, language = {en} } @article{KochAchterbergAndersenetal.2011, author = {Koch, Thorsten and Achterberg, Tobias and Andersen, Erling and Bastert, Oliver and Berthold, Timo and Bixby, Robert E. and Danna, Emilie and Gamrath, Gerald and Gleixner, Ambros and Heinz, Stefan and Lodi, Andrea and Mittelmann, Hans and Ralphs, Ted and Salvagnin, Domenico and Steffy, Daniel and Wolter, Kati}, title = {MIPLIB 2010}, series = {Mathematical Programming Computation}, volume = {3}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-011-0025-9}, pages = {103 -- 163}, year = {2011}, 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} }