naa a22 4500 510809057 CHVBK 20180411083433.0 cr unu---uuuuu 180411e20130901xx s 000 0 eng 10.1007/s12532-013-0055-6 doi (NATIONALLICENCE)springer-10.1007/s12532-013-0055-6 A hybrid branch-and-bound approach for exact rational mixed-integer programming [Elektronische Daten] [William Cook, Thorsten Koch, Daniel Steffy, Kati Wolter] 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. Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society, 2013 Mixed integer programming nationallicence Branch-and-bound nationallicence Exact computation nationallicence Cook William School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA aut Koch Thorsten Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany aut Steffy Daniel Department of Mathematics and Statistics, Oakland University, Rochester, MI, USA aut Wolter Kati Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany aut Mathematical Programming Computation Springer Berlin Heidelberg 5/3(2013-09-01), 305-344 1867-2949 5:3<305 2013 5 12532 https://doi.org/10.1007/s12532-013-0055-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s12532-013-0055-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Cook William School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA aut NATIONALLICENCE 700 1- Koch Thorsten Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany aut NATIONALLICENCE 700 1- Steffy Daniel Department of Mathematics and Statistics, Oakland University, Rochester, MI, USA aut NATIONALLICENCE 700 1- Wolter Kati Zuse Institute Berlin, Takustr. 7, 14195, Berlin, Germany aut NATIONALLICENCE 773 0- Mathematical Programming Computation Springer Berlin Heidelberg 5/3(2013-09-01), 305-344 1867-2949 5:3<305 2013 5 12532 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer