Repository: DepositOnce â€“ institutional repository for research data and publications of TU Berlin https://depositonce.tu-berlin.de
@phdthesis { 11303_11067,
author = {Jarck, Kati},
title = {Exact mixed-integer programming},
school = {Technische UniversitÃ¤t Berlin},
year = {2020},
type = {Doctoral Thesis},
address = {Berlin},
doi = {10.14279/depositonce-9955},
url = {http://dx.doi.org/10.14279/depositonce-9955},
keywords = {mixed-integer programming, numerical analysis, hybrid approach, safe dual bounds, iterative refinement, gemischt-ganzzahlige Optimierung, numerische Analyse, hybrider Ansatz, sichere Dualschranken, iteratives Refinement},
abstract = {In this thesis, we develop and implement an efficient algorithm that can exactly solve instances of the mixed-integer programming problem that are given by rational data. For a feasible instance, a truly optimal solution will be computed; for an infeasible instance, a provably correct infeasibility certificate will be issued. Our exact mixed-integer programming solver is part of the constraint integer programming software SCIP, which is developed and maintained at the Zuse Institute Berlin.
Mixed-integer programming solvers have experienced tremendous progress in the last decades, while almost no attention has been paid to exact computations. Most mixed-integer programming solvers, in particular, the state-of-the-art ones CPLEX, Gurobi, MOSEK, SCIP, and Xpress, are numerical solvers, i.e., they use finite-precision binary floating-point arithmetic, which is a compromise between speed and correctness. Such solvers cannot provide any guarantee of correct results. Due to a number of reasons, for many industrial applications near optimal solutions are sufficient. This situation changes fundamentally when mixed-integer programming is used to establish theoretical results, when feasibility questions are considered, and when serious legal and financial consequences may result from incorrect solutions.
To underline the necessity of exact solvers, this thesis, first, analyzes how strong the error-proneness inherent in finite-precision binary floating-point systems influences the results of numerical mixed-integer programming solvers. We employ two important theoretical concepts from numerical mathematics therefor: condition of a problem instance and stability of an algorithm. In addition, we test the stability of SCIP on the Miplib benchmarking libraries, discuss how to identify instances of the mixed-integer programming problem on which current solvers face numerical difficulties, and build the first large test set of numerically difficult instances.
This thesis, then, shows that it is possible to solve instances of the mixed-integer programming problem exactly over the rational numbers without introducing a large overhead in running time compared to solving them numerically. This applies to numerically easy as well as to numerically difficult instances. While earlier attempts in that direction showed slow-downs of orders of magnitudes, we provide the first efficient exact branch-and-bound solver. As our focus is exclusively on the branch-and-bound procedure, we compared the exact solver against a numerical solver restricted to pure branch-and-bound. The key ingredients of the exact solver are as follows. The first one is the new hybrid rational/safe floating-point approach. The second one is to dynamically choose the fastest of several safe dual bounding methods depending on the structure of the instance. The third one is the sophisticated integration of iterative refinement for linear programming, a new technique to improve the stability of numerical linear programming solvers, into the solution process of the exact mixed-integer programming solver.}
}