Solving Mixed-Integer Linear and Nonlinear Network Optimization Problems by Local Reformulations and Relaxations

Language
en
Document Type
Doctoral Thesis
Issue Date
2018-03-06
Issue Year
2017
Authors
Merkert, Maximilian
Editor
Abstract

Since the beginnings of network optimization, the number of use cases has grown enormously and can be expected to further expand in an increasingly interconnected world. The wide range of modern applications include optimization tasks on energy networks, telecommunication networks and in public transport, just to name a few. Although many traditional network optimization problems are NP-hard in their basic version, applications pose additional challenges due to more complicated — often nonlinear — dependencies or the sheer size of the network. In this thesis, we develop methods that help to cope with those challenges. A common strategy will be to improve mathematical programming formulations locally by modeling substructures in an integrated way. The resulting reformulations and relaxations will allow for global methods that either solve the problem to exact optimality or up to a predefined precision. For large-scale network expansion problems, a solution method is proposed that is based on iterative aggregation. Starting with an initial aggregation, we solve a sequence of network design problems over increasingly fine-grained representations of the original network. This is done until the whole network is represented sufficiently well in the sense that an optimal solution to the aggregated problem can easily be extended to an optimal solution of the original problem. Global optimality is guaranteed by a subproblem that computationally is less expensive and either proves optimality or gives an indication of where to refine the representation. In this algorithmic scheme, locally relaxing the problem allows us to focus on the critical part of the network. In many optimization problems on transportation networks — especially those arising from energy applications — the main challenge is connected to the problem’s nonlinear features, arising, for example, from laws of physics. Gas networks represent a typical example for such a nonlinear network flow setting that we will repeatedly refer to throughout this work. A common and established solution approach consists of constructing a piecewise linear approximation or relaxation. We study how to strengthen the resulting mixed-integer programming formulation for specific substructures in the network. We find effective cutting planes and derive a complete description for induced paths of arbitrary length — using graph-theoretic arguments related to perfect graphs. A generalization of key properties of this special case leads to an abstract definition in terms of clique problems on a specific type of graph. This abstract setting also comprises a basic version of the project scheduling problem and still allows us to give totally unimodular reformulations that are of linear size. Moreover, questions regarding recognizability of this structure will be discussed. We also discuss the concept of simultaneous convexification that can be seen as a continuous counterpart to our approach for piecewise linearized problems. The resulting reformulations can improve relaxations employed by general-purpose MINLP solvers, which usually rely on convexifying nonlinear functions separately. Computational results demonstrate the practical impact of the methods developed in this thesis, in many cases using real-world data sets.

Abstract

Seit den Anfängen der Netzwerkoptimierung ist die Zahl der Anwendungsfälle immens gewachsen und angesichts einer zunehmend vernetzten Welt ist ein weiterer Anstieg zu erwarten. Die Spannbreite moderner Anwendungen umfasst Optimierungsprobleme auf Energienetzen, Telekommunikationsnetzen und Verkehrsnetzen, um nur einige zu nennen. Auch wenn viele traditionelle Netzwerkoptimierungsprobleme bereits in ihrer Grundversion NP-schwer sind, stellen Anwendungen weitere Anforderungen aufgrund komplexerer - oftmals nichtlinearer - Abhängigkeiten oder der schieren Größe der zugrunde liegenden Netzwerke. In dieser Arbeit werden Methoden entwickelt, um mit diesen Herausforderungen umzugehen. Die wesentliche Strategie wird darin bestehen, mathematische Problemformulierungen lokal zu verstärken, indem ausgewählte Substrukturen als Ganzes erfasst und modelliert werden. Die resultierenden Reformulierungen und Relaxierungen unterstützen globale Methoden, die entweder exakte oder bis auf eine vordefinierte Genauigkeit optimale Lösungen finden. Für große Netzausbauprobleme wird eine Lösungsmethodik basierend auf iterativer Aggregation entworfen. Beginnend mit einer Startaggregation lösen wir eine Folge zunehmend detaillierter Vergröberungen des ursprünglichen Netzwerks, bis die Darstellung hinreichend genau ist, sodass seine Optimallösung leicht auf das ursprüngliche Problem übertragen werden kann. Exaktheit wird dabei durch ein Subproblem sichergestellt, das entweder Optimalität bestätigt oder Ansatzpunkte zur Verfeinerung der Darstellung liefert. In diesem Schema erlaubt somit eine lokale Relaxierung die Fokussierung auf kritische Teile des Netzwerks. In vielen Optimierungsproblemen auf Transportnetzen, insbesondere für Energieträger, besteht die wesentliche Herausforderung in den auftretenden Nichtlinearitäten, die beispielsweise physikalischen Gesetzen geschuldet sind. Gasnetwerke sind hierfür ein typisches Beispiel, auf das wir uns mehrfach in dieser Arbeit beziehen werden. Ein etablierter Lösungsansatz besteht in der Konstruktion stückweise linearer Approximationen oder Relaxierungen. Es wird untersucht, wie die entstehende Formulierung für bestimmte Substrukturen verstärkt werden kann. Dabei finden wir effektive Schnittebenen und leiten mittels graphentheoretischer Argumente eine vollständige Beschreibung für induzierte Pfade her. Eine Abstraktion wesentlicher Eigenschaften dieses Spezialfalls führt auf Cliquenprobleme auf bestimmten Graphen. Dieser abstrakte Rahmen umfasst auch eine Basisversion des Projektplanungsproblems und erlaubt es weiterhin, eine total unimodulare Reformulierung von linearer Größe nachzuweisen. Weiterhin werden Fragen zur Erkennbarkeit dieser Struktur behandelt. Außerdem wird das Konzept der simultanen Konvexifizierung diskutiert, das als kontinuierliches Gegenstück zu unserem Ansatz für stückweise linearisierte Probleme angesehen werden kann. Die entstehenden Reformulierungen verstärken Relaxierungen, auf die allgemeine MINLP-Löser typischerweise angewiesen sind. Rechenergebnisse unter Einbeziehung realer Datensätze zeigen den praktischen Einfluss der in dieser Arbeit entwickelten Methoden.

DOI
Faculties & Collections
Zugehörige ORCIDs