Adaptive gemischt-ganzzahlige Verfeinerungen zur Lösung nichtlinearer Probleme mit diskreten Entscheidungen

Many optimization problems in science and technology are subject to a system of nonlinear constraints combined with discrete decisions. Mathematically, these problems can be modeled as mixed-integer nonlinear programs (MINLPs), since they can represent both nonlinear correlations and discrete decisions. However, the interaction of integrality and nonlinearity poses a major challenge in solving these problems. In this thesis, we propose a method for solving MINLPs to global optimality by discretization of the occurring nonlinearities. Our approach requires only continuous nonlinearities with bounded domains and is thus suitable for a wide range of MINLP problems. The emphasis is on using sophisticated and reliable mixed-integer linear programming technology to solve MINLPs. Similarly to the solution of mixed-integer linear programs (MIPs), which relies on solving linear programming relaxations, we develop a framework for solving MINLPs by MIP relaxations. To this end, we use piecewise linear functions to construct MIP relaxations of the underlying MINLP. An iterative algorithm constructs MIP relaxations that are subsequently refined and solved until a globally optimal solution is found. The refinement of the nonlinearities is crucial for the outcome of the algorithm. For that reason, we study different refinement strategies with a focus on embedding them in our adaptive MIP-based framework. We prove convergence results for the presented refinement methods. In addition, we present first results on the size of an MIP relaxation that is required to achieve an a priori given accuracy for the nonlinearities. Finally, we illustrate the practicalness of our approach by numerical results for MINLPs that are difficult to solve by state-of-the-art global MINLP solvers. These problems arise in the context of gas transport network optimization and optimal power flow. They combine non-convex nonlinearities that describe certain physical phenomena with integer restrictions that model discrete decisions for switchable elements. Such elements are, for instance, compressors in case of gas networks or generator units in case of power networks. On the basis of theses MINLP instances, we demonstrate the advantage of our approach over other global MINLP solvers.Viele Optimierungsprobleme der Wissenschaft und Technik werden anhand eines Systems nichtlinearer Restriktionen in Kombination mit diskreten Entscheidungen gelöst. Mathematisch lassen sich diese Probleme als gemischt-ganzzahlige nichtlineare Programme (MINLPs) modellieren, da diese sowohl nichtlineare Zusammenhänge als auch diskrete Entscheidungen darstellen können. Das Zusammenspiel von Ganzzahligkeit und Nichtlinearität stellt dabei eine große Herausforderung bei der Lösung dieser Probleme dar. In dieser Arbeit behandeln wir eine Methode zur global optimalen Lösung von MINLPs durch Diskretisierung der auftretenden Nichtlinearitäten. Unser Ansatz erfordert nur kontinuierliche Nichtlinearitäten mit beschränktem Definitionsbereich und ist daher für eine Vielzahl von MINLP-Problemen geeignet. Die grundlegende Idee hierbei ist, ausgereifte und zuverlässige Technologie der gemischt-ganzzahligen Programmierung zur Lösung von MINLPs einzusetzen. Ähnlich wie das Lösen von gemischt-ganzzahligen linearen Programmen (MIPs) auf der Lösung linearer Programme, d.h. von Relaxierungen der MIPs, beruht, entwickeln wir einen Ansatz zur Lösung von MINLPs, der auf der Lösung von MIP-Relaxierungen beruht. Hierzu verwenden wir stückweise lineare Funktionen, um MIP-Relaxierungen des zugrunde liegenden MINLPs zu konstruieren. Der iterative Algorithmus konstruiert MIP-Relaxierungen, die abwechselnd verfeinert und gelöst werden, bis eine global optimale Lösung gefunden wird. Die Verfeinerung der Nichtlinearitäten ist entscheidend für die Konvergenz und Korrektheit des Algorithmus. Aus diesem Grund untersuchen wir verschiedene Verfeinerungsstrategien mit dem Schwerpunkt auf deren Einbettung in unseren adaptiven MIP-basierten Ansatz. Wir liefern zunächst Konvergenzresultate für die vorgestellten Verfeinerungsmethoden. Darüber hinaus leiten wir erste Ergebnisse zur Größe einer MIP-Relaxierung her, die benötigt wird, um eine a priori gegebene Genauigkeit für die Nichtlinearitäten zu erreichen. Abschließend veranschaulichen wir die Anwendbarkeit unseres Ansatzes in der Praxis durch numerische Ergebnisse für MINLPs, die mit den modernsten globalen MINLP-Lösern nur schwer zu lösen sind. Diese Probleme entstehen im Kontext der Gastransportoptimierung und der optimalen Lastflussberechnung. Sie kombinieren nichtkonvexe Nichtlinearitäten, die spezifische physikalische Phänomene beschreiben, mit ganzzahligen Restriktionen, die diskrete Entscheidungen für schaltbare Elemente modellieren. Solche Elemente sind beispielsweise Kompressoren bei Gasnetzwerken oder Generatoreinheiten bei Stromnetzwerken. Anhand dieser MINLP-Instanzen zeigen wir den Mehrwert unseres Ansatzes gegenüber anderen globalen MINLP-Lösern auf