Structure Exploitation in Mixed-Integer Optimization with Applications to Energy Systems

Das Ziel dieser Arbeit ist neue numerische Methoden für gemischt-ganzzahlige Optimierungsprobleme zu entwickeln um eine verbesserte Geschwindigkeit und Skalierbarkeit zu erreichen. Dies erfolgt durch Ausnutzung gängiger Problemstrukturen wie separierbarkeit oder Turnpike-eigenschaften. Methoden, die diese Strukturen ausnutzen können, wurden bereits im Bereich der verteilten Optimierung und optimalen Steuerung entwickelt, sie sind jedoch nicht direkt auf gemischt-ganztägige Probleme anwendbar.

Um verteilte Rechenressourcen zur Lösung von gemischt-ganzzahligen Problemen nutzen zu können, sind neue Methoden erforderlich. ... mehrZu diesem Zweck werden verschiedene Erweiterungen bestehender Methoden sowie neuartige Techniken zur gemischt-ganzzahligen Optimierung vorgestellt.

Benchmark-Probleme aus Strom- und Energiesystemen werden verwendet, um zu demonstrieren, dass die vorgestellten Methoden zu schnelleren Laufzeiten führen und die Lösung großer Probleme ermöglichen, die sonst nicht zentral gelöst werden können. Die vorliegende Arbeit enthält die folgenden Beiträge:

- Eine Erweiterung des Augmented Lagrangian Alternating Direction Inexact Newton-Algorithmus zur verteilten Optimierung für gemischt-ganzzahlige Probleme.

- Ein neuer, teilweise-verteilter Optimierungsalgorithmus für die gemischt-ganzzahlige Optimierung basierend auf äußeren Approximationsverfahren.

- Ein neuer Optimierungsalgorithmus für die verteilte gemischt-ganzzahlige Optimierung, der auf branch-and-bound Verfahren basiert.

- Eine erste Untersuchung von Turnpike-Eigenschaften bei Optimalsteuerungsproblemen mit gemischten-Ganzzahligen Entscheidungsgrößen und ein spezieller Algorithmus zur Lösung dieser Probleme.

- Eine neue Branch-and-Bound Heuristik, die a priori Probleminformationen effizienter nutzt als aktuelle Warmstarttechniken.

Schließlich wird gezeigt, dass die Ergebnisse der vorgestellten Optimierungsalgorithmen für verteilte gemischt-ganzzahlige Optimierung stark Partitionierungsabhängig sind. Zu diesem Zweck wird auch eine Untersuchung von Partitionierungsmethoden für die verteilte Optimierung vorgestellt.

The goal of this thesis is to develop new numerical methods for mixed-integer optimization problems and achieve improved speed and scalability. This is done by exploiting common problem structures, such as separability or turnpike behaviour. Methods capable of exploiting these structures have already been developed in the realms of distributed optimization and optimal control, however they are not directly applicable to the mixed-integer case.

To be able to make use of distributed computing resources to solve mixed-integer problems, new methods are required. To this end, several extensions of existing methods as well as novel techniques for mixed-integer optimization are presented.
... mehr
Benchmark problems drawn from power and energy systems are used to demonstrate that the presented methods can lead to faster runtimes and can allow for solution to large problems that are otherwise impossible to solve in a centralized manner. The novelties presented in this thesis are as follows:

- Extension of the Augmented Lagrangian Alternating Direction Inexact Newton distributed optimization algorithm applicable to mixed-integer optimization.

- A new partially distributed mixed-integer optimization algorithm based on outer approximation.

- A new distributed mixed-integer optimization algorithm based on branch and bound.

- A first investigation into turnpike properties in mixed-integer optimal control and a specialized algorithm for solving this class of problems.

- A new branch and bound heuristic that more efficiently exploits a priori problem information than current warm-starting techniques.

Finally, it is shown that the results of the presented distributed mixed-integer optimization algorithms can heavily depend on how a given problem is partitioned. To this effect, an investigation into partitioning methods for distributed optimization is also given.