Publication Date:
2020-11-16
Description:
The amazing success of computational mathematical optimization over
the last decades has been driven more by insights into mathematical
structures than by the advance of computing technology. In this vein,
we address applications, where nonconvexity in the model and
uncertainty in the data pose principal difficulties.
The first part of the thesis deals with non-convex quadratic programs.
Branch&Bound methods for this problem class depend on tight
relaxations. We contribute in several ways: First, we establish a new
way to handle missing linearization variables in the well-known
Reformulation-Linearization-Technique (RLT). This is implemented
into the commercial software CPLEX. Second, we study the optimization
of a quadratic objective over the standard simplex or a knapsack
constraint. These basic structures appear as part of many complex
models. Exploiting connections to the maximum clique problem and RLT,
we derive new valid inequalities. Using exact and heuristic separation
methods, we demonstrate the impact of the new inequalities on the
relaxation and the global optimization of these problems. Third, we
strengthen the state-of-the-art relaxation for the pooling problem, a
well-known non-convex quadratic problem, which is, for example,
relevant in the petrochemical industry. We propose a novel relaxation
that captures the essential non-convex structure of the problem but is
small enough for an in-depth study. We provide a complete inner
description in terms of the extreme points as well as an outer
description in terms of inequalities defining its convex hull (which
is not a polyhedron). We show that the resulting valid convex
inequalities significantly strengthen the standard relaxation of the
pooling problem.
The second part of this thesis focuses on a common challenge in real
world applications, namely, the uncertainty entailed in the input
data.
We study the extension of a gas transport network, e.g., from our
project partner Open Grid Europe GmbH.
For a single scenario this maps to a challenging non-convex MINLP.
As the future transport patterns are highly uncertain, we propose a
robust model to best prepare the network operator for an array of
scenarios.
We develop a custom decomposition approach that makes use of the
hierarchical structure of network extensions and the loose coupling
between the scenarios.
The algorithm used the single-scenario problem as black-box subproblem
allowing the generalization of our approach to problems with the same
structure.
The scenario-expanded version of this problem is out of reach for
today's general-purpose MINLP solvers.
Yet our approach provides primal and dual bounds for instances with up
to 256 scenarios and solves many of them to optimality.
Extensive computational studies show the impact of our work.
Description:
Der bemerkenswerte Erfolg der angewandten mathematischen Optimierung
in den letzten Dekaden ist mehr auf Einsichten in mathematische
Strukturen zurückzuführen, als auf eine Steigerung der Rechenleistung.
In diesem Sinne adressieren wir Anwendungen, in denen Nichtkonvexität
und Unsicherheit in den Daten die Hauptschwierigkeiten darstellen.
Der erste Teil dieser Arbeit beschäftigt sich mit nichtkonvexen
quadratischen Optimierungsproblemen. Relaxierungen sind integraler
Bestandteil von \BranchAndBound{}-Lösungsmethoden für diese
Problemkategorie. Wir leisten folgende Beiträge: Erstens beschreiben
wir eine neue Art fehlende Linearisierungsvariablen, in der so
genannten Reformulation-Linearization-Technique (RLT), zu behandeln.
Diese wird inzwischen in der kommerziellen Software CPLEX verwendet.
Zweitens beschäftigen wir uns mit der Optimierung einer quadratischen
Zielfunktion über die Standardsimplex oder einen so genannten
Knapsack-Constraint. Solche grundlegenden Strukturen sind Teil vieler
komplexer Modelle. Wir benutzen bekannte Verbindungen zum maximalen
Cliquenproblem sowie zu RLT, um neue gültige Ungleichungen
herzuleiten, die die Relaxierung verstärken. Drittens beschäftigen wir uns mit dem
Pooling Problem, das z.B. in der Erdölindustrie relevant ist. Wie
leiten eine neue Relaxierung her, die die wesentliche nicht-konvexe
Struktur des Problems erfasst, aber klein genug für eine grundlegende
Untersuchung ist. Wir geben eine innere Beschreibung in Form der
Extrempunkte, sowie eine äußere Beschreibung in Form von Ungleichungen,
die die konvexe Hülle (welche im Allgemeinen kein Polyeder ist)
beschreiben, an. Wir zeigen, dass neuen die Ungleichungen die Relaxierung
des Pooling Problems erheblich verstärken.
Der zweite Teil der Arbeit befasst sich mit einer weiteren
Herausforderung in realen Anwendungen, nämlich Unsicherheit in den
Eingabedaten. Konkret untersuchen wir die Optimierung des Ausbaus
eines Gastransportnetzes, wie z.B. von unserem Projektpartner Open
Grid Europe GmbH. Dieses Problem ist bereits bei gegebenen
Eingabedaten ein schweres nicht-konvexes gemischt-ganzzahliges
Optimierungsproblem. Da zukünftige Nutzungsmuster des Netzes mit
großer Unsicherheit behaftet sind, beschreiben wir ein robustes
Modell, um den Netzbetreiber gegen verschiedene Szenarien abzusichern.
Wir entwickeln einen speziellen Dekompositionsalgorithmus unter
Berücksichtigung der hierarchischen Struktur der Ausbauten und der
schwachen Kopplung zwischen den Szenarien. Unser Ansatz liefert primale
und duale Schranken für Instanzen mit bis
zu 256 Szenarien und löst viele beweisbar optimal.
Umfangreiche Rechnungen bestätigen die Effizient der
vorgestellten Methoden.
Language:
English
Type:
doctoralthesis
,
doc-type:doctoralThesis
Permalink
