ISBN 9783843953238

978-3-8439-5323-8, Reihe Mathematik

Matthias Miltenberger
Linear Programming in MILP Solving - A Computational Perspective

237 Seiten, Dissertation Technische Universität Berlin (2023), Hardcover, B5

Zusammenfassung / Abstract

Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. This thesis explores the impact of various LP solvers as well as LP solving techniques on the SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers, as well as commercially developed, high-end codes. We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD. This visualization technique facilitates a better understanding of the MILP solving process of SCIP. Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP's internal data structures from Python to implement custom algorithms and extensions without writing C code. All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on GitHub.