<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <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>
