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

Lösungsmethoden für gemischt-ganzzahlige lineare und nichtlineare Netzwerkoptimierungsprobleme basierend auf lokalen Reformulierungen und Relaxierungen

Please always quote using this URN: urn:nbn:de:bvb:29-opus4-94035
  • 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 programmingSince 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.show moreshow less
  • 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. DieSeit 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.show moreshow less

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Maximilian Merkert
URN:urn:nbn:de:bvb:29-opus4-94035
Referee:Frauke Liers, Rüdiger Schultz, Christoph Helmberg
Document Type:Doctoral Thesis
Language:English
Year of Completion:2017
Embargo Date:2018/02/26
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Granting Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Naturwissenschaftliche Fakultät
Date of final exam:2017/11/02
Release Date:2018/03/06
Tag:Aggregation; Gas network optimization; Network design; Perfect graphs; Piecewise linear functions; Simultaneous Convexification; Staircase Compatibility
SWD-Keyword:Gemischt-ganzzahlige Optimierung; Netzwerkfluss
Pagenumber:169
Institutes:Naturwissenschaftliche Fakultät
Dewey Decimal Classification:Naturwissenschaften und Mathematik / Mathematik / Wahrscheinlichkeiten, angewandte Mathematik
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C21 Flows in graphs
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C69 Dominating sets, independent sets, cliques
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming
open_access (DINI-Set):open_access
Licence (German):Keine Creative Commons Lizenz - es gilt der Veröffentlichungsvertrag und das deutsche Urheberrecht