Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 3 von 4
Zurück zur Trefferliste

An Exact Rational Mixed-Integer Programming Solver

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-12329
  • 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:William Cook, Thorsten KochORCiD, Daniel SteffyORCiD, Kati Wolter
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:branch-and-bound; exact computation; mixed integer programming
MSC-Klassifikation:65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-08 Computational methods
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
CCS-Klassifikation:G. Mathematics of Computing / G.4 MATHEMATICAL SOFTWARE
Datum der Erstveröffentlichung:10.03.2011
Schriftenreihe (Bandnummer):ZIB-Report (11-07)
ZIB-Reportnummer:11-07
Verlagspublikation:Appeared in: IPCO 2011: Proceedings of the 15th International Conference on Integer Programming and Combinatoral Optimization. Oktay Gün et al. (eds.) Springer 2011. LNCS 6655. ISBN 978-3-642-20806-5. Pp. 104-106. DOI 10.1007/978-3-642-20807-2_9
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.