<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>8932</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName>TU Berlin</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Mathematical programming for stable control and safe operation of gas transport networks</title>
    <abstract language="eng">The fight against climate change makes extreme but inevitable changes in the energy sector necessary. These in turn lead to novel and complex challenges for the transmission system operators (TSOs) of gas transport networks. In this thesis, we consider four different planning problems emerging from real-world operations and present mathematical programming models and solution approaches for all of them.&#13;
Due to regulatory requirements and side effects of renewable energy production, controlling today's gas networks with their involved topologies is becoming increasingly difficult. Based on the network station modeling concept for approximating the technical capabilities of complex subnetworks, e.g., compressor stations, we introduce a tri-level MIP model to determine important global control decisions. Its goal is to avoid changes in the network elements' settings while deviations from future inflow pressures as well as supplies and demands are minimized. A sequential linear programming inspired post-processing routine is run to derive physically accurate solutions w.r.t. the transient gas flow in pipelines. Computational experiments based on real-world data show that meaningful solutions are quickly and reliably determined. Therefore, the algorithmic approach is used within KOMPASS, a decision support system for the transient network control that we developed together with the Open Grid Europe GmbH (OGE), one of Europe's largest natural gas TSOs.&#13;
Anticipating future use cases, we adapt the aforementioned algorithmic approach for hydrogen transport. We investigate whether the natural gas infrastructure can be repurposed and how the network control changes when energy-equivalent amounts of hydrogen are transported. Besides proving the need for purpose-built compressors, we observe that, due to the reduced linepack, the network control becomes more dynamic, compression energy increases by 440% on average, and stricter regulatory rules regarding the balancing of supply and demand become necessary.&#13;
Extreme load flows expose the technical limits of gas networks and are therefore of great importance to the TSOs. In this context, we introduce the Maximum Transportation Problem and the Maximum Potential Transport Moment Problem to determine severe transport scenarios. Both can be modeled as linear bilevel programs where the leader selects supplies and demands, maximizing the follower's transport effort. To solve them, we identify solution-equivalent instances with acyclic networks, provide variable bounds regarding their KKT reformulations, apply the big-M technique, and solve the resulting MIPs. A case study shows that the obtained scenarios exceed the maximum severity values of a provided test set by at least 23%.&#13;
OGE's transmission system is 11,540km long. Monitoring it is crucial for safe operations. To this end, we discuss the idea of using uncrewed aerial vehicles and introduce the Length-Constrained Cycle Partition Problem to optimize their routing. Its goal is to find a smallest cycle partition satisfying vertex-induced length requirements. Besides a greedy-style heuristic, we propose two MIP models. Combining them with symmetry-breaking constraints as well as valid inequalities and lower bounds from conflict hypergraphs yields a highly performant solution algorithm for this class of problems.</abstract>
    <identifier type="url">https://doi.org/10.14279/depositonce-15837</identifier>
    <identifier type="doi">10.14279/depositonce-15837</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <advisor>Thorsten Koch</advisor>
    <author>Kai Hoppmann-Baum</author>
    <submitter>Kai Hoppmann-Baum</submitter>
    <collection role="persons" number="hennig">Hoppmann, Kai</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>9326</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>2023-12-01</thesisDateAccepted>
    <title language="eng">Cutting Plane Selection for Mixed-Integer Linear Programming</title>
    <abstract language="eng">Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions. &#13;
&#13;
Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67% of affected MIPLIB 2017 instances by 4%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97% of affected MIPLIB 2017 instances by 5%.</abstract>
    <enrichment key="opus.source">publish</enrichment>
    <advisor>Thorsten Koch</advisor>
    <author>Mark Turner</author>
    <submitter>Mark Turner</submitter>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cutting Planes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cut Selection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Machine Learning</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="turner">Turner, Mark Ruben</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="projects" number="UNSEEN">UNSEEN</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>9108</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>2023-05-17</thesisDateAccepted>
    <title language="eng">Modeling and solving real-world transient gas network transport problems using mathematical programming</title>
    <abstract language="eng">This thesis considers the transient gas network control optimization problem for on-shore pipeline-based transmission networks with numerous gas routing options.&#13;
As input, the problem is given the network's topology, its initial state, and future demands at the boundaries of the network, which prescribe the gas flow exchange and potentially the pressure values.&#13;
The task is to find a set of future control measures for all the active, i.e., controllable, elements in the network that minimizes a combination of different penalty functions.&#13;
The problem is examined in the context of a decision support tool for gas network dispatchers.&#13;
This results in detailed models featuring a diverse set of constraints, large and challenging real-world instances, and demanding time limit requirements.&#13;
All these factors further complicate the problem, which is already difficult to solve in theory due to the inherent combination of non-linear and combinatorial aspects.&#13;
&#13;
Our contributions concern different steps of the process of solving the problem.&#13;
Regarding the model formulation, we investigate the validity of two common approximations of the gas flow description in transport pipes: neglecting the inertia term and assuming a friction term that linearly depends on the gas flow and the pressure.&#13;
For both, we examine if they can be applied under real-world conditions by evaluating a large amount of historical state data of the network of our project partner, the gas network operator Open Grid Europe.&#13;
While we can confirm that it is reasonable to ignore the influence of the inertia term, the friction term linearization leads to significant errors and, as a consequence, cannot be used for describing the general gas flow behavior in transport pipes.&#13;
&#13;
As another topic of this thesis, we introduce the target value concept as a more realistic approach to express control actions of dispatchers regarding regulators and compressor stations.&#13;
Here, we derive the mechanisms defined for target values based on the gas flow principles in pipes and develop a mixed-integer programming model capturing their behavior.&#13;
The accuracy of this model is demonstrated in comparison to a target-value-based industry-standard simulator.&#13;
Furthermore, we present two heuristics for the transient gas network control optimization problem featuring target values that are based on approximative models for the target-value-based control and determine the final decisions in a post-processing step.&#13;
To compare the performance of the two heuristics with the approach of directly solving the corresponding model, we evaluate them on a set of artificially created test instances.&#13;
&#13;
Finally, we develop problem-specific algorithms for two variants of the described problem.&#13;
One considers the control optimization for a single network station, which represents a local operation site featuring a large number of active elements.&#13;
The used transient model is very detailed and includes a sophisticated representation of the compressor stations.&#13;
Based on the shortness of the pipes in the station, the corresponding algorithm finds valid solutions by solving a series of stationary model variants as well as a transient rolling horizon approach.&#13;
As the second variant, we consider the problem on the entire network but assume an approximative model representing the control capabilities of network stations.&#13;
Aside from a new description of the compression capabilities, we introduce an algorithm that uses a combination of sequential mixed-integer programming, two heuristics based on reduced time horizons, and a specialized dynamic branch-and-bound node limit to determine promising values for the binary variables of the model.&#13;
Complete solutions for the problem are obtained by fixing the binary values and solving the remaining non-linear program.&#13;
Both algorithms are investigated in extensive empirical studies based on real-world instances of the corresponding model variants.</abstract>
    <abstract language="deu">Diese Arbeit behandelt das Optimierungsproblem der transienten Gasnetzwerksteuerung von Fernleitungsnetzen auf dem Festland mit einer großen Anzahl möglicher Gastransportrouten.&#13;
Die Eingabedaten bestehen aus der Netzwerktopologie, dem Anfangszustand des Netzes und zukünftigen Vorgaben an den Randknoten des Netzes, welche den Gaseinfluss und Gasausfluss sowie eine potenzielle Vorgabe von Druckwerten umfassen.&#13;
Gegeben diese Daten besteht die Aufgabe besteht darin, eine Menge an zukünftigen Steuerungsentscheidungen für alle aktiven, also steuerbaren, Elemente des Netzes zu finden, sodass eine Kombination von Straffunktionen minimiert wird.&#13;
Das Problem wird in dieser Arbeit im Rahmen der Erstellung eines entscheidungsunterstützenden Systems für Dispatcher betrachtet, welche das Gasnetz steuern.&#13;
Dies resultiert in einer detaillierten Modellierung mit einer Vielzahl von Nebenbedingungen, großen und herausfordernden realistischen Instanzen sowie anspruchsvollen Vorgaben zur maximalen Laufzeit.&#13;
Diese Eigenschaften erhöhen die Komplexität des Problems, welches bereits in der Theorie auf Grund der inhärenten Kombination von nichtlinearen und kombinatorischen Aspekten schwierig zu lösen ist.&#13;
&#13;
Die Beiträge dieser Arbeit betreffen verschiedene Schritte des Prozesses zur Lösung des Problems.&#13;
Bezüglich der Modellformulierung werden zwei übliche Approximationen der Gasflussbeschreibung in Fernleitungsrohren auf Validität überprüft:&#13;
die Vernachlässigung des Trägheitsterms und die Annahme einer linearisierten Beschreibung des Reibungsterms.&#13;
Für beide Approximationen wird untersucht, ob sie für reale Gasflussbedingungen zulässig sind.&#13;
Dazu wird eine große Anzahl historischer Netzzustandsdaten des Gasnetzbetreibers Open Grid Europe ausgewertet.&#13;
Während bestätigt werden kann, dass eine Vernachlässigung des Trägheitsterms unter Realbedingungen angemessen ist, führt die Linearisierung des Reibungsterms zu signifikanten Fehlern und kann daher nicht für die allgemeine Beschreibung des Gasflusses in Fernleitungsrohren verwendet werden.&#13;
&#13;
In einem weiteren Teil dieser Arbeit wird das Konzept der Sollwerte eingeführt.&#13;
Mit diesen ist eine realistischere Beschreibung der Steuerungsbefehle möglich, welche den Dispatchern für Regler und Verdichterstationen zur Verfügung stehen.&#13;
Der Sollwertmechanismus wird basierend auf den Gasflussprinzipien in Rohrleitungen hergeleitet, um anschließend ein gemischt-ganzzahliges Programm zu entwickeln, welches das entsprechende Verhalten erzeugt.&#13;
Die Präzision dieses Modells wird durch einen Vergleich mit einem Simulator von Industriestandard sichergestellt, welcher auf Sollwerten basiert.&#13;
Außerdem werden zwei Heuristiken für das Optimierungsproblem der transienten Gasnetzwerksteuerung mit Sollwertmodellierung vorgestellt.&#13;
Diese basieren auf approximativen Modellen für die Sollwertsteuerung und ermitteln die letztendlichen Steuerungsentscheidungen in einer nachgelagerten Routine.&#13;
Basierend auf künstlich erzeugten Testinstanzen werden die Heuristiken schließlich mit dem direkten Lösen des entsprechenden Modells verglichen.&#13;
&#13;
Zudem werden in dieser Arbeit problemspezifische Algorithmen für zwei Varianten des beschriebenen Optimierungsproblems entwickelt.&#13;
Die erste Variante betrachtet das Gasnetzwerksteuerungsproblem beschränkt auf eine einzelne Netzstation, die lokale Betriebsstellen darstellen und über eine Vielzahl an aktiven Steuerungselementen verfügen.&#13;
Das entsprechende transiente Modell ist sehr detailliert und beinhaltet eine differenzierte Beschreibung der Verdichterstationen.&#13;
Der problemspezifische Algorithmus basiert auf der Kürze der Rohre innerhalb der Station und findet zulässige Lösungen durch das Lösen von stationären Varianten des Modells sowie der Nutzung eines transienten Rolling-Horizon Ansatzes.&#13;
In der zweiten Problemvariante wird das gesamte Gasnetz betrachtet, wobei eine vereinfachte Modellierung der Steuerungsmöglichkeiten innerhalb von Netzstationen angenommen wird.&#13;
Neben einer neuen Beschreibung der Verdichtungsmöglichkeiten einer Station wird ebenfalls ein problemspezifischer Algorithmus entwickelt.&#13;
Dieser erstellt aussichtsreiche Werte für die Binärvariablen und nutzt dafür eine Kombination aus sequenzieller gemischt-ganzzahliger Programmierung, zwei auf verkürzten Zeithorizonten basierenden Heuristiken und eine spezialisierte dynamische Obergrenze für die Anzahl der Branch-and-Bound-Knoten.&#13;
Diese Teillösungen werden durch eine Fixierung der binären Variablen und das anschließende Lösen des restlichen nichtlinearen Programms komplettiert.&#13;
Die Güte beider Algorithmen wird in umfangreichen empirischen Experimenten untersucht, welche reale Instanzen der jeweiligen Problemvarianten betrachten.</abstract>
    <enrichment key="opus.source">publish</enrichment>
    <advisor>Thorsten Koch</advisor>
    <author>Felix Hennings</author>
    <submitter>Felix Hennings</submitter>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="projects" number="MODAL-EnergyLab">MODAL-EnergyLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>5327</id>
    <completedYear>2014</completedYear>
    <publishedYear>2014</publishedYear>
    <thesisYearAccepted>2014</thesisYearAccepted>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2014-11-22</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>2014-11-06</thesisDateAccepted>
    <title language="eng">Gas Network Optimization by MINLP</title>
    <abstract language="eng">One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. The challenging question is how to expand and operate the network in order to facilitate the transportation of specified gas quantities at minimum cost. This task can be formulated as a mathematical optimization problem that reflects to real-world instances of enormous size and complexity. The aim of this thesis is the development of novel theory and optimization algorithms which make it possible to solve these problems. &#13;
&#13;
Gas network topology optimization problems can be modeled as nonlinear mixed-integer programs (MINLPs). Such an MINLP gives rise to a so-called active transmission problem (ATP), a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. The key to solving the ATP as well as the overall gas network topology optimization problem and the main contribution of this thesis is a novel domain relaxation of the variable bounds and constraints in combination with a penalization in the objective function. In case the domain relaxation does not yield a primal feasible solution for the ATP we offer novel sufficient conditions for proving the infeasibility of the ATP. These conditions can be expressed in the form of an MILP, i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. &#13;
&#13;
If the gas network consists only of pipes and valves, the ATP turns into a passive transmission problem (PTP). Although its constraints are non-convex, its domain relaxation can be proven to be convex. Consequently, the feasibility of the PTP can be checked directly in an efficient way. Another advantage of the passive case is that the solution of the domain relaxation gives rise to a cutting plane for the overall topology optimization problem that expresses the infeasibility of the PTP. This cut is obtained by a Benders argument from the Lagrange function of the domain relaxation augmented by a specially tailored pc-regularization. These cuts provide tight lower bounds for the passive gas network topology optimization problem. &#13;
&#13;
The domain relaxation does not only provide certificates of infeasibility and cutting planes, it can also be used to construct feasible primal solutions. We make use of parametric sensitivity analysis in order to identify binary variables to be switched based on dual information. This approach allows for the first time to compute directly MINLP solutions for large-scale gas network topology optimization problems. &#13;
&#13;
All the research in this thesis has been realized within the collaborative research project "Forschungskooperation Netzoptimierung (ForNe)". The developed software is in use by the cooperation partner Open Grid Europe GmbH. &#13;
&#13;
Parts of this thesis have been published in book chapters, journal articles and technical reports. An overview of the topics and solution approaches within the research project is given by Martin et al. (2011) and Fügenschuh et al. (2013). Gas network operation approaches and solution methods are described in detail by Pfetsch et al. (2014) and with a special focus on topology optimization in Fügenschuh et al. (2011). The primal heuristic presented in this thesis is published by Humpola et al. (2014b). The method for pruning nodes of the branch-and-bound tree for an approximation of the original problem is described in Fügenschuh and Humpola (2013) and Humpola et al. (2014a). The Benders like inequality is introduced by Humpola and Fügenschuh (2013).</abstract>
    <abstract language="deu">Ein Viertel des europäischen Energiebedarfs wird durch Gas gedeckt, das durch ein europaweites Pipelinesystem verteilt wird. Aufgrund von Ausbaukosten von 1 Mio. Euro pro Kilometer ist der Netzausbau ein Milliardenunterfangen. Die größte Herausforderung besteht darin zu entscheiden, wie das Netzwerk kostengünstig ausgebaut und genutzt werden kann, um notwendige Gasmengen zu transportieren. Diese Aufgabe kann mit Hilfe eines mathematischen Optimierungsproblems formuliert werden, wobei anwendungsnahe Instanzen eine enorme Größe und Komplexität aufweisen. Ziel der vorliegenden Arbeit ist die Entwicklung neuer mathematischer Theorien und damit einhergehender Optimierungsalgorithmen, die es ermöglichen, derartige Probleme zu lösen. &#13;
&#13;
Die Optimierung der Topologie eines Gasnetzwerks kann mit Hilfe eines nichtlinearen gemischt-ganzzahligen Programms (MINLP) modelliert werden. Durch Fixierung aller ganzzahligen Variablen ergibt sich ein kontinuierliches Zulässigkeitsproblem, das als aktives Transmissionsproblem (ATP) bezeichnet wird. Die zentrale Methode um dieses ATP zu lösen, ist eine neuartige Relaxierung, welche Variablenschranken und einige Nebenbedingungen relaxiert und in der Zielfunktion bestraft. Diese Relaxierung bildet den Kern der in dieser Arbeit vorgestellten Theorie und ermöglicht so die effiziente Lösung der Topologieoptimierung eines Gasnetzwerkes. Für den Fall, dass die Relaxierung keine Primallösung für das ATP liefert, ist es uns gelungen, hinreichende Bedingungen für die Unzulässigkeit des ATP zu formulieren, die durch ein MILP dargestellt werden. Kurz gefasst kann die Unzulässigkeit eines nicht-konvexen NLP durch Lösung eines MILP bewiesen werden. Beide Methoden liefern effiziente Schranken in einem branch-and-bound Lösungsverfahren. &#13;
&#13;
Besteht ein Gasnetzwerk nur aus Rohren und Schiebern, dann wird das ATP als passives Transmissionsproblem (PTP) bezeichnet. Obwohl die Nebenbedingungen des PTP nicht konvex sind, konnten wir zeigen, dass seine Relaxierung konvex ist. Daher kann die Unzulässigkeit des PTP direkt auf effiziente Weise geprüft werden. Außerdem können mit Hilfe der Relaxierung in diesem speziellen Fall Schnittebenen für das Topologieoptimierungsproblem aufgestellt werden. Diese repräsentieren die Unzulässigkeit des PTP und folgen aus der Lagrange Funktion der Relaxierung zusammen mit einer speziellen Erweiterung, der sogenannten pc-Regularisierung. &#13;
&#13;
Abgesehen von den genannten Klassifizierungen kann die Relaxierung auch genutzt werden, um primale Lösungen zu konstruieren. Hier nutzen wir die parametrische Sensitivitätsanalyse, um mit Hilfe dualer Informationen Binärvariablen des ATP zu identifizieren, deren Werte angepasst werden müssen. Dieser Ansatz erlaubt es zum ersten Mal, direkt MINLP Lösungen für das Topologieoptimierungsproblem realer Gasnetzwerke zu berechnen. &#13;
&#13;
Die Resultate dieser Arbeit wurden im Rahmen des Forschungsprojekts "Forschungskooperation Netzoptimierung (ForNe)" erarbeitet. Die entwickelte Software wird vom Kooperationspartner Open Grid Europe GmbH aktiv genutzt. &#13;
&#13;
Teile dieser Arbeit sind in Buchkapiteln, Journalen und technischen Berichten publiziert. Eine Übersicht über die Themen und Lösungsansätze im ForNe-Projekt veröffentlichten Martin u. a. (2011) und Fügenschuh u. a. (2013). Für Lösungsmethoden für die operative Nutzung von Gasnetzwerken verweisen wir auf Pfetsch u. a. (2014). Ansätze für eine Topologieoptimierung wurden von Fügenschuh u. a. (2011) beschrieben. Die in dieser Arbeit präsentierte primale Heuristik ist publiziert von Humpola u. a. (2014b). Die genannte Methode, um Knoten innerhalb des branch-and-bound Baums abzuschneiden, wurde für eine Approximation des Topologieproblems von Fügenschuh und Humpola (2013) und Humpola u. a. (2014a) beschrieben. Ein Bericht über die Ungleichungen nach Benders ist in Humpola und Fügenschuh (2013) nachzulesen.</abstract>
    <additionalTitle language="deu">Gas Netzwerk Optimierung mittels MINLP</additionalTitle>
    <identifier type="url">http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/5904</identifier>
    <advisor>Martin Grötschel</advisor>
    <submitter>Jesco Humpola</submitter>
    <referee>Martin Grötschel</referee>
    <author>Jesco Humpola</author>
    <referee>Thorsten Koch</referee>
    <referee>Andrea Lodi</referee>
    <collection role="msc" number="05-XX">COMBINATORICS (For finite fields, see 11Txx)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="ForNe">ForNe</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisPublisher>Technische Universität Berlin</thesisPublisher>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>6691</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>411</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>2017-02-03</thesisDateAccepted>
    <title language="eng">Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty</title>
    <abstract language="eng">The amazing success of computational mathematical optimization over&#13;
the last decades has been driven more by insights into mathematical&#13;
structures than by the advance of computing technology. In this vein,&#13;
we address applications, where nonconvexity in the model and&#13;
uncertainty in the data pose principal difficulties.&#13;
&#13;
The first part of the thesis deals with non-convex quadratic programs.&#13;
Branch&amp;Bound methods for this problem class depend on tight&#13;
relaxations. We contribute in several ways: First, we establish a new&#13;
way to handle missing linearization variables in the well-known&#13;
Reformulation-Linearization-Technique (RLT). This is implemented&#13;
into the commercial software CPLEX. Second, we study the optimization&#13;
of a quadratic objective over the standard simplex or a knapsack&#13;
constraint. These basic structures appear as part of many complex&#13;
models. Exploiting connections to the maximum clique problem and RLT,&#13;
we derive new valid inequalities. Using exact and heuristic separation&#13;
methods, we demonstrate the impact of the new inequalities on the&#13;
relaxation and the global optimization of these problems. Third, we&#13;
strengthen the state-of-the-art relaxation for the pooling problem, a&#13;
well-known non-convex quadratic problem, which is, for example,&#13;
relevant in the petrochemical industry. We propose a novel relaxation&#13;
that captures the essential non-convex structure of the problem but is&#13;
small enough for an in-depth study. We provide a complete inner&#13;
description in terms of the extreme points as well as an outer&#13;
description in terms of inequalities defining its convex hull (which&#13;
is not a polyhedron). We show that the resulting valid convex&#13;
inequalities significantly strengthen the standard relaxation of the&#13;
pooling problem.&#13;
&#13;
The second part of this thesis focuses on a common challenge in real&#13;
world applications, namely, the uncertainty entailed in the input&#13;
data.&#13;
We study the extension of a gas transport network, e.g., from our&#13;
project partner Open Grid Europe GmbH.&#13;
For a single scenario this maps to a challenging non-convex MINLP.&#13;
As the future transport patterns are highly uncertain, we propose a&#13;
robust model to best prepare the network operator for an array of&#13;
scenarios.&#13;
We develop a custom decomposition approach that makes use of the&#13;
hierarchical structure of network extensions and the loose coupling&#13;
between the scenarios.&#13;
The algorithm used the single-scenario problem as black-box subproblem&#13;
allowing the generalization of our approach to problems with the same&#13;
structure.&#13;
The scenario-expanded version of this problem is out of reach for&#13;
today's general-purpose MINLP solvers.&#13;
Yet our approach provides primal and dual bounds for instances with up&#13;
to 256 scenarios and solves many of them to optimality.&#13;
&#13;
Extensive computational studies show the impact of our work.</abstract>
    <abstract language="deu">Der bemerkenswerte Erfolg der angewandten mathematischen Optimierung&#13;
in den letzten Dekaden ist mehr auf Einsichten in mathematische&#13;
Strukturen zurückzuführen, als auf eine Steigerung der Rechenleistung.&#13;
In diesem Sinne adressieren wir Anwendungen, in denen Nichtkonvexität&#13;
und Unsicherheit in den Daten die Hauptschwierigkeiten darstellen.&#13;
&#13;
Der erste Teil dieser Arbeit beschäftigt sich mit nichtkonvexen&#13;
quadratischen Optimierungsproblemen. Relaxierungen sind integraler&#13;
Bestandteil von \BranchAndBound{}-Lösungsmethoden für diese&#13;
Problemkategorie. Wir leisten folgende Beiträge: Erstens beschreiben&#13;
wir eine neue Art fehlende Linearisierungsvariablen, in der so&#13;
genannten Reformulation-Linearization-Technique (RLT), zu behandeln.&#13;
Diese wird inzwischen in der kommerziellen Software CPLEX verwendet.&#13;
Zweitens beschäftigen wir uns mit der Optimierung einer quadratischen&#13;
Zielfunktion über die Standardsimplex oder einen so genannten&#13;
Knapsack-Constraint. Solche grundlegenden Strukturen sind Teil vieler&#13;
komplexer Modelle. Wir benutzen bekannte Verbindungen zum maximalen&#13;
Cliquenproblem sowie zu RLT, um neue gültige Ungleichungen&#13;
herzuleiten, die die Relaxierung verstärken. Drittens beschäftigen wir uns mit dem&#13;
Pooling Problem, das z.B. in der Erdölindustrie relevant ist. Wie&#13;
leiten eine neue Relaxierung her, die die wesentliche nicht-konvexe&#13;
Struktur des Problems erfasst, aber klein genug für eine grundlegende&#13;
Untersuchung ist. Wir geben eine innere Beschreibung in Form der&#13;
Extrempunkte, sowie eine äußere Beschreibung in Form von Ungleichungen,&#13;
die die konvexe Hülle (welche im Allgemeinen kein Polyeder ist)&#13;
beschreiben, an. Wir zeigen, dass neuen die Ungleichungen die Relaxierung&#13;
des Pooling Problems erheblich verstärken.&#13;
&#13;
Der zweite Teil der Arbeit befasst sich mit einer weiteren&#13;
Herausforderung in realen Anwendungen, nämlich Unsicherheit in den&#13;
Eingabedaten. Konkret untersuchen wir die Optimierung des Ausbaus&#13;
eines Gastransportnetzes, wie z.B. von unserem Projektpartner Open&#13;
Grid Europe GmbH. Dieses Problem ist bereits bei gegebenen&#13;
Eingabedaten ein schweres nicht-konvexes gemischt-ganzzahliges&#13;
Optimierungsproblem. Da zukünftige Nutzungsmuster des Netzes mit&#13;
großer Unsicherheit behaftet sind, beschreiben wir ein robustes&#13;
Modell, um den Netzbetreiber gegen verschiedene Szenarien abzusichern.&#13;
Wir entwickeln einen speziellen Dekompositionsalgorithmus unter&#13;
Berücksichtigung der hierarchischen Struktur der Ausbauten und der&#13;
schwachen Kopplung zwischen den Szenarien. Unser Ansatz liefert primale &#13;
und duale Schranken für Instanzen mit bis&#13;
zu 256 Szenarien und löst viele beweisbar optimal.&#13;
&#13;
Umfangreiche Rechnungen bestätigen die Effizient der&#13;
vorgestellten Methoden.</abstract>
    <identifier type="url">http://dx.doi.org/10.14279/depositonce-6015</identifier>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <advisor>Thorsten Koch</advisor>
    <author>Jonas Schweiger</author>
    <submitter>Jonas Schweiger</submitter>
    <advisor>Andrea Lodi</advisor>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Nonconvexity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Uncertainty</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Quadratic Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Relaxations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cutting Planes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Standard Quadratic Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Pooling Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Gas Network Planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Robust Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Decomposition</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Computations</value>
    </subject>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="msc" number="90C20">Quadratic programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-GasLab">MODAL-GasLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="schweiger">Schweiger, Jonas</collection>
    <collection role="institutes" number="enernet">Energy Network Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
</export-example>
