<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1042</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>Graduiertenkolleg MAGSI</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-11-30</completedDate>
    <publishedDate>2007-11-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Multicommodity Routing Problems-Selfish Behavior and Online Aspects-</title>
    <abstract language="eng">In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones.</abstract>
    <abstract language="deu">Diese Arbeit befasst sich mit Mehrgüterﬂussproblemen, in denen Güter mit einer bestimmten Rate durch ein gegebenes Netzwerk geleitet werden müssen. Mithilfe von Mehrgüterﬂussproblemen können zum Beispiel Verkehrsﬂüsse in Strassenverkehrsnetzen oder im Internet modelliert werden. In diesen Anwendungen wird die Efﬁzienz von Routenzuweisungen für Güter durch lastabhängige Kostenfunktionen auf den Kanten eines gegebenen Netzwerks deﬁniert. Die Gesamtkosten eines Mehrgüterﬂüsses sind durch die Summe der Kosten auf den Kanten deﬁniert. Ein optimaler Mehrgüterﬂuss minimiert diese Gesamtkosten. Ein wesentlicher Bestandteil dieser Arbeit ist die Untersuchung sogenannter Online Algorithmen, die Routen für bekannte Güternachfragen berechnen, ohne vollständiges Wissen über zukünftige Güternachfragen zu haben. Es konnte ein Online Algorithmus gefunden werden, dessen Gesamtkosten für polynomielle Kostenfunktionen mit endlichem Grad nicht beliebig von denen einer optimalen Lösung abweichen. Für die Berechung einer optimalen Lösung müssen alle Güternachfragen a priori vorliegen. Dieses Gütekriterium gilt unabhängig von der gewählten Netzwerktopologie oder der Eingabesequenz von Gütern. Desweiteren befasst sich diese Arbeit mit der Efﬁzienz egoistischer Routenwahl einzelner Nutzer verglichen zu einer optimalen Routenwahl. Egoistisches Verhalten von Nutzern kann mithilfe von nichtkooperativer Spieltheorie untersucht werden. Nutzer werden als strategisch agierende Spieler betrachtet, die ihren Proﬁt maximieren. Als Standardwerkzeug zur Analyse solcher Spiele hat sich das Konzept des Nash Gleichgewichts bewährt. Das Nash Gleichweicht beschreibt eine stabile Strategieverteilung der Spieler, in der kein Spieler einen höheren Proﬁt erzielen kann, wenn er einseitig seine Strategie ändert. Als Hauptergebnis dieser Arbeit konnte für polynomielle Kostenfunktionen mit endlichem Grad gezeigt werden, dass die Gesamtkosten eines Nash Gleichgewichts für sogennante atomare Spieler, die einen diskreten Anteil der gesamten Güternachfrage kontrollieren, nicht beliebig von den Gesamtkosten einer optimalen Lösung abweichen. In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones.</abstract>
    <identifier type="isbn">3867273596</identifier>
    <identifier type="opus3-id">1070</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10426</identifier>
    <enrichment key="SourceTitle">Cuvillier Verlag, Berlin, 2007 ISBN-10: 3867273596, ISBN-13: 9783867273596</enrichment>
    <author>Tobias Harks</author>
    <submitter>unknown unknown</submitter>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mehrgueterflussprobleme</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Algorithmische Spieltheorie.</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multicommodity Flow</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Algorithmic Game Theory</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90Cxx">Mathematical programming [See also 49Mxx, 65Kxx]</collection>
    <collection role="msc" number="91-XX">GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1042/harks_thesis_revised.pdf</file>
  </doc>
  <doc>
    <id>1060</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2006-07-20</completedDate>
    <publishedDate>2006-07-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Kombinatorische Optimierung –Inhalte und Methoden für einen authentischen Mathematikunterricht</title>
    <abstract language="deu">wird nachgereicht</abstract>
    <identifier type="opus3-id">1089</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10608</identifier>
    <author>Brigitte Lutz-Westphal</author>
    <submitter>unknown unknown</submitter>
    <advisor>J. M. Sullivan</advisor>
    <advisor>Martin Grötschel</advisor>
    <advisor>U. Kortenkamp</advisor>
    <advisor>J. Krämer</advisor>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1060/LutzWestphalDiss.pdf</file>
  </doc>
  <doc>
    <id>1018</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-10-15</completedDate>
    <publishedDate>2007-10-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming</title>
    <abstract language="eng">This thesis introduces the novel paradigm of constraint integer programming (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method.</abstract>
    <abstract language="deu">Diese Arbeit stellt einen integrierten Ansatz aus Constraint Programming (CP) und Gemischt-Ganzzahliger Programmierung (Mixed Integer Programming, MIP) vor, den wir Constraint Integer Programming (CIP) nennen. Sowohl Modellierungs- als auch Lösungstechniken beider Felder fließen in den neuen integrierten Ansatz ein, um die unterschiedlichen Stärken der beiden Gebiete zu kombinieren. Als weiteren Beitrag stellen wir der wissenschaftlichen Gemeinschaft die Software SCIP zur Verfügung, die ein Framework für Constraint Integer Programming darstellt und zusätzlich Techniken des SAT-Lösens beinhaltet. SCIP ist im Source Code für akademische und nicht-kommerzielle Zwecke frei erhältlich. Unser Ansatz des Constraint Integer Programming ist eine Verallgemeinerung von MIP, die zusätzlich die Verwendung beliebiger Constraints erlaubt, solange sich diese durch lineare Bedingungen ausdrücken lassen falls alle ganzzahligen Variablen auf feste Werte eingestellt sind. Die Constraints werden von einer beliebigen Kombination aus CP- und MIP-Techniken behandelt. Dies beinhaltet insbesondere die Domain Propagation, die Relaxierung der Constraints durch lineare Ungleichungen, sowie die Verstärkung der Relaxierung durch dynamisch generierte Schnittebenen. Die derzeitige Version von SCIP enthält alle Komponenten, die für das effiziente Lösen von Gemischt-Ganzzahligen Programmen benötigt werden. Die vorliegende Arbeit liefert eine ausführliche Beschreibung dieser Komponenten und bewertet verschiedene Varianten in Hinblick auf ihren Einfluß auf das Gesamt-Lösungsverhalten anhand von aufwendigen praktischen Experimenten. Dabei wird besonders auf die algorithmischen Aspekte eingegangen. Der zweite Hauptteil der Arbeit befasst sich mit der Chip-Design-Verifikation, die ein wichtiges Thema innerhalb des Fachgebiets der Electronic Design Automation darstellt. Chip-Hersteller müssen sicherstellen, dass der logische Entwurf einer Schaltung der gegebenen Spezifikation entspricht. Andernfalls würde der Chip fehlerhaftes Verhalten aufweisen, dass zu Fehlfunktionen innerhalb des Gerätes führen kann, in dem der Chip verwendet wird. Ein wichtiges Teilproblem in diesem Feld ist das Eigenschafts-Verifikations-Problem, bei dem geprüft wird, ob der gegebene Schaltkreisentwurf eine gewünschte Eigenschaft aufweist. Wir zeigen, wie dieses Problem als Constraint Integer Program modelliert werden kann und geben eine Reihe von problemspezifischen Algorithmen an, die die Struktur der einzelnen Constraints und der Gesamtschaltung ausnutzen. Testrechnungen auf Industrie-Beispielen vergleichen unseren Ansatz mit den bisher verwendeten SAT-Techniken und belegen den Erfolg unserer Methode.</abstract>
    <identifier type="opus3-id">1038</identifier>
    <identifier type="urn">urn:nbn:de:kobv:83-opus-16117</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <advisor>Martin Grötschel</advisor>
    <advisor>Robert E. Bixby</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Chip-Verifikation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chip verification</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="ccs" number="B.8.1">Reliability, Testing, and Fault-Tolerance (NEW)</collection>
    <collection role="ccs" number="G.1.6">Optimization</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1018/achterberg_tobias.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1018/Achterberg_Constraint_Integer_ProgrammingDissZweite_Vers.pdf</file>
  </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>5305</id>
    <completedYear/>
    <publishedYear>2014</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>2014-07-28</thesisDateAccepted>
    <title language="eng">Robust tail assignment</title>
    <abstract language="eng">The first part of this thesis is devoted to the general problem of stochastic shortest path problem. It is about searching for the shortest path in a graph in which arc lengths are uncertain and specified by continuous random variables. This problem is at the core of various applications, especially in robust transportation planning where paths correspond to aircraft, train, or bus rotations, crew duties or rosters, etc. We propose a novel solution method based on a discretisation of random variables which is applicable to any class of continuous random variables. We also give bounds on the approximation error of the discretised path lengths compared to the continuous path lengths. In addition, we provide theoretical results for the computational complexity of this method. In the second part we apply this method to a real world airline transportation problem: the so-called tail assignment problem. The goal of the tail assignment problem is to construct aircraft rotations, routes consisting of flight segments, for a set of individual aircraft in order to cover a set of flight segments (legs) while considering operational constraints of each individual aircraft as well as short- to long-term individual maintenance requirements. We state a stochastic programming formulation of this problem and we show how to solve it efficiently by using our method within a column generation framework. We show the gain of our stochastic approach in comparison to standard KPI in terms of less propagated delay and thus less operational costs without growth of computational complexity. A key point of our complex approach to robust optimisation problem is the fit of the underlying stochastic model with reality. We propose a delay propagation model that is realistic, not overfitted, and can therefore be used for forecasting purposes. We benchmark our results using extensive simulation. We show a significant decrease of arrival delays and thus monetary savings on average as well as in the majority of our disruption scenarios. We confirm these benefits in even more life-like benchmarks as simulation where recovery actions are taken and in scenarios which use historical delays directly instead of the stochastic model.</abstract>
    <identifier type="url">http://opus4.kobv.de/opus4-tuberlin/frontdoor/index/index/docId/5664</identifier>
    <advisor>Ralf Borndörfer</advisor>
    <author>Ivan Dovica</author>
    <submitter> Neumann</submitter>
    <advisor>Martin Grötschel</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Flugzeug-Umlaufplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Spaltenerzeugung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Verspätungspropagation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>delay propagation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>stochastic shortest path problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>tail assignment</value>
    </subject>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="LHS-rxOPT-tail">LHS-rxOPT-tail</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>4939</id>
    <completedYear/>
    <publishedYear>2011</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>2011-10-19</thesisDateAccepted>
    <title language="eng">Applied Methods for the Vehicle Positioning Problem</title>
    <abstract language="eng">This dissertation is dedicated to the Vehicle Positioning Problem (VPP), a classical combinatorial optimization problem in public transport in which vehicles should be assigned to parking positions in a depot in such a way that shunting moves are minimized. We investigate several models and solution methods to solve the VPP and the VPPp, a multi-periodic extension of the problem which was not previously studied. In the first part of the thesis, the basic version of the problem is introduced and several formulations, theoretical properties, and concepts are investigated. In particular, we propose a mixed integer quadratic constrained formulation of the VPP whose QP relaxation produces the first known nontrivial lower bound on the number of shunting moves. The second part of our work describes two advanced solution methods. In the first approach, a set partitioning formulation is solved by a branch-and-price framework. We present efficient algorithms for the pricing problem and in order to improve the performance of the framework, we introduce heuristics and discuss strategies to reduce symmetry. The second approach consists of an iterative technique in which we try to optimize an ILP by solving some of its projections, which are smaller and therefore easier to compute. Both techniques are able to produce satisfactory solutions for large-scale instances of the VPPp. In the third part, advanced aspects of the problem are investigated. We propose and analyze several solution methods for the VPP+ and for the VPPp+, which are extended and more challenging versions of the VPP and of the VPPp, respectively. Finally, the role of uncertainty in the problem is discussed. In particular, we introduce a new criteria to evaluate the robustness of assignment plans, a formulation based on this concept, and a new online algorithm for the VPP.</abstract>
    <identifier type="urn">urn:nbn:de:kobv:83-opus-34211</identifier>
    <advisor>Martin Grötschel</advisor>
    <author>Carlos Cardonha</author>
    <submitter> Engel</submitter>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>1040</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-06-14</completedDate>
    <publishedDate>2007-06-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Design of Survivable Optical Networks by Mathematical Optimization</title>
    <abstract language="eng">Abstract The cost-efficient design of survivable optical telecommunication networks is the topic of this thesis. In cooperation with network operators, we have developed suitable concepts and mathematical optimization methods to solve this comprehensive planning task in practice. Optical technology is more and more employed in modern telecommunication networks. Digital information is thereby transmitted as short light pulses through glass fibers. Moreover, the optical medium allows for simultaneous transmissions on a single fiber by use of different wavelengths. Recent optical switches enable a direct forwarding of optical channels in the network nodes without the previously required signal retransformation to electronics. Their integration creates ongoing optical connections,which are called lightpaths. We study the problem of finding cost-efficient configurations of optical networks which meet specified communication requirements. A configuration comprises the determination of all lightpaths to establish as well as the detailed allocation of all required devices and systems. We use a flexible modeling framework for a realistic representation of the networks and their composition. For different network architectures, we formulate integer linear programs which model the design task in detail. Moreover, network survivability is an important issue due to the immense bandwidths offered by optical technology. Operators therefore request for designs which perpetuate protected connections and guarantee for a defined minimum throughput in case of malfunctions. In order to achieve an effective realization of scalable protection, we present a novel survivability concept tailored to optical networks and integrate several variants into the models. Our solution approach is based on a suitable model decomposition into two subtasks which separates two individually hard subproblems and enables this way to compute cost-efficient designs with approved quality guarantee. The first subtask consists of routing the connections with corresponding dimensioning of capacities and constitutes a common core task in the area of network planning. Sophisticated methods for such problems have already been developed and are deployed by appropriate integration. The second subtask is characteristic for optical networks and seeks for a conflict-free assignment of available wavelengths to the lightpaths using a minimum number of involved wavelength converters. For this coloring-like task, we derive particular models and study methods to estimate the number of unavoidable conversions. As constructive approach, we develop heuristics and an exact branch-and-price algorithm. Finally, we carry out an extensive computational study on realistic data, provided by our industrial partners. As twofold purpose, we demonstrate the potential of our approach for computing good solutions with quality guarantee, and we exemplify its flexibility for application to network design and analysis.</abstract>
    <identifier type="opus3-id">1074</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10408</identifier>
    <enrichment key="SourceTitle">Ersch. als Buchveröffentlichung: Design of Survivable Optical Networks by Mathematical Optimization, (2007), Cuvillier, ISBN 978-3-86727-253-7.</enrichment>
    <author>Adrian Zymolka</author>
    <submitter>unknown unknown</submitter>
    <advisor>U. Pinkall</advisor>
    <advisor>Martin Grötschel</advisor>
    <advisor>Sven Krumke</advisor>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>network design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optical networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mathematical optimization</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1040/Dissertation_Zymolka.pdf</file>
  </doc>
  <doc>
    <id>2840</id>
    <completedYear>1998</completedYear>
    <publishedYear>1998</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>TU Berlin</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Aspects of Set Packing, Partitioning, and Covering</title>
    <identifier type="url">http://opus.kobv.de/zib/volltexte/1998/1028/</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-10126</enrichment>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>1027</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1996-12-31</completedDate>
    <publishedDate>1996-12-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Polyhedral Subdivisions and Projections of Polytopes</title>
    <abstract language="eng">The present dissertation deals with the structure of polyhedral subdivisions of point configurations. Of particular interest are the global properties of the set of all subdivisions of a given point configuration. An important open problem in this context is the following: can one always transform any triangulation of a given point configuration to any other triangulation of the same configuration by means of bistellar operations? In other words, is the set of all triangulations of a given point configuration always bistellarly connected? The results presented in this thesis contribute progress from two directions. \begin{itemize} \item The set of all subdivisions that are induced by a polytope projection is in general not bistellarly connected in a generalized sense. This result is obtained by constructing a counterexample to the so-called Generalized Baues Conjecture.'' \item The set of all triangulations of a cyclic polytope forms a bounded poset. The covering relations are given by increasing bistellar operations. Thus we get an affirmative answer to the above question in the case of cyclic polytopes. \end{itemize} In the introduction, the mathematical environment of the structures under consideration is illuminated. The "Generalized Baues Conjecture" has connections to various mathematical concepts, such as combinatorial models for loop spaces, discriminants of polynomials in several variables, etc. The triangulation posets of cyclic polytopes are natural generalizations of the well-studied Tamari lattices in order theory. Moreover, there is a connection to the higher Bruhat orders, which have similar structural properties. As a by-product, the investigations yield the shellability of all triangulations of cyclic polytopes without new vertices. This is in particular interesting because most triangulations of cyclic polytopes are non-regular.</abstract>
    <abstract language="deu">Die vorliegende Dissertation beschäftigt sich mit strukturellen Fragen in der Theorie der polyedrischen Unterteilungen von Punktkonfigurationen. Hierbei sind vor allem globale Eigenschaften der Menge aller Unterteilungen einer gegebenen Punktkonfiguration von Interesse. Eine wichtige ungelöste Frage in diesem Zusammenhang ist die folgende: Ist es immer möglich, von einer beliebigen Triangulierung einer gegebenen Punktkonfiguration zu jeder anderen Triangulierung derselben Konfiguration zu gelangen, indem man sogenannte bistellare Operationen durchführt? Mit anderen Worten, ist die Menge aller Triangulierungen einer gegebenen Punktkonfiguration stets bistellar zusammenhängend? Die Ergebnisse der vorliegenden Doktorarbeit liefern auf zwei Seiten dieser nach wie vor offenen Frage Fortschritte: \begin{itemize} \item Die Menge aller durch eine Polytopprojektion induzierten Unterteilungen ist nicht immer --- in einem verallgemeinerten Sinne --- bistellar zusammenhängend. Dieses Resultat wird durch ein Gegenbeispiel zur sogenannten "Verallgemeinerten Baues Vermutung"' erzielt. \item Die Menge aller Triangulierungen eines zyklischen Polytops bildet eine beschränkte Halbordnung. Die Ueberdeckungsrelationen sind gerichtete bistellare Operationen. Für zyklische Polytope ist die obige Frage nach bistellarem Zusammenhang also positiv beantwortet. \end{itemize} In der Einleitung wird das mathematische Umfeld der betrachteten Strukturen näher beleuchtet: Die "Verallgemeinerte Baues Vermutung" steht in Verbindung mit verschiedensten mathematischen Konzepten, angefangen von kombinatorischen Modellen von Schleifenräumen bis hin zu Diskriminanten von Polynomen in mehreren Variablen. Die Triangulierungs-Halbordnungen von zyklischen Polytopen sind zugleich natürliche Verallgemeinerungen der gut studierten Tamari-Verbände in der Ordnungstheorie. Ausserdem existiert ein Zusammenhang mit den höheren Bruhat-Ordnungen, die ähnliche Struktureigenschaften aufweisen. Ein Nebenprodukt der Untersuchungen ist die Schälbarkeit aller Triangulierungen von zyklischen Polytopen ohne neue Ecken. Das ist um so interessanter, da die meisten Triangulierungen von zyklischen Polytopen nicht-regulär sind.</abstract>
    <identifier type="isbn">3-8265-1955-8</identifier>
    <identifier type="opus3-id">1052</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10271</identifier>
    <enrichment key="SourceTitle">Ersch. als Buchveröffentlichung: Jörg Rambau: Polyhedral Subdivisions and Projections of Polytopes, Shaker Verlag, Aachen, 1996, 137 Seiten.</enrichment>
    <author>Jörg Rambau</author>
    <submitter>unknown unknown</submitter>
    <advisor>Günter M. Ziegler</advisor>
    <advisor>Raimund Seidel</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>polyedrische Unterteilung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Triangulierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Verallgemeinertes Baues-Problem</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Zyklisches Polytop</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Höhere Bruhat-Ordnung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedral subdivision</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>triangulation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Generalized Baues Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cyclic polytope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>higher Bruhat order</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="52B11">n-dimensional polytopes</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="msc" number="52C35">Arrangements of points, flats, hyperplanes [See also 32S22]</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1027/diss_MASTER.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1027/diss.ps</file>
  </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>
