Mathematical optimization for optimal decision-making in practice : Energy systems and political districting

Goderbauer, Sebastian; Lübbecke, Marco (Thesis advisor); Koster, Arie Marinus (Thesis advisor); Pukelsheim, Friedrich (Thesis advisor)

Aachen (2019, 2020)
Doktorarbeit

Dissertation, Rheinisch-Westfälische Technische Hochschule Aachen, 2019

Kurzfassung

Das Treffen von Entscheidungen kann eine komplexe Aufgabe sein. So gibt es beispielsweise eine enorme Anzahl an Möglichkeiten, Fahrzeuge eines Logistikunternehmens zu routen, Stundenpläne für eine Universität festzulegen oder Standorte für Ladestationen für Elektroautos zu definieren. Für eine Problemstellung können mehr Entscheidungsalternativen existieren als Partikel im gesamten Universum. Diese kombinatorische Explosion ist nicht nur auf die großen Datenmengen zurückzuführen, die beteiligt sein können. Vielfältige Abhängigkeiten zwischen (Teil-)Entscheidungen, unterschiedliche Bedingungen und Kriterien beeinflussen ebenfalls die Komplexität. In den meisten Fällen und insbesondere, wenn man an einer bestmöglichen Entscheidung interessiert ist, ist es hoffnungslos, komplexe Entscheidungsprobleme von Hand oder durch einfache Enumeration mit dem Computer zu lösen. Die Mathematik und insbesondere ihr Teilgebiet die mathematische Optimierung bieten Konzepte, Methoden und eine Forschungsumgebung zur Bewältigung komplexer Entscheidungsprobleme. Die Mathematik ermöglicht es den Entscheidungstragenden, eine nachweislich bestmögliche Lösung zu finden, die dann in der Praxis umgesetzt werden kann. Dies führt zu einer wachsenden Anzahl von Erfolgsgeschichten durch Anwendung mathematischer Optimierung: Zum Beispiel, um Geld zu sparen, den Umweltschutz zu verbessern, Fairness zu gewährleisten oder Leben zu retten. In dieser Dissertation werden zwei Anwendungsfelder mit dem Ziel einer optimalen Entscheidungsfindung bearbeitet. Die beiden Anwendungen repräsentieren das breite Spektrum der Gebiete, in denen Mathematik zu besseren, transparenteren und/oder objektiveren Entscheidungen führen kann. Die erste Anwendung beinhaltet die Optimierung von dezentralen Energiesystemen. Die Aufgabe besteht darin, ein System aus verschiedenen Energieumwandlungstechnologien zu bestimmen, das in der Lage ist, einen Bedarf an verschiedenen Energieformen zu erfüllen. Ein optimal ausgelegtes dezentrales Energiesystem kann für große Industrieanlagen, Krankenhäuser, Forschungseinrichtungen oder auch Wohnsiedlungen vorteilhaft sein. Darüber hinaus können auch ökologische Vorteile erzielt werden. Der Beitrag dieser Arbeit umfasst die Entwicklung einer Lösungsmethode, die nicht-lineare und nicht-konvexe Technologiemodelle berücksichtigt. Dieses Merkmal unterscheidet die vorgeschlagene Methode von den meisten in der Literatur vorgeschlagenen. Die überwiegende Mehrheit der in der Literatur präsentierten Ansätze vernachlässigt, dass physikalische, chemische und technische Zusammenhänge natürlicherweise nicht-linear sind. Die vorgeschlagene Lösungsmethode basiert auf einem entwickelten adaptiven Diskretisierungsansatz und liefert qualitativ hochwertige Lösungen für auf realen Daten basierende Instanzen. Als weiterer Beitrag werden die ersten Ergebnisse zur Komplexität des Problems bewiesen. Die Resultate rechtfertigen die Entwicklung von Lösungsmethoden mit potentiell exponentieller Laufzeit. Eine solche fundierte Begründung fehlt bis heute. Die zweite Anwendung beinhaltet die optimale Einteilung von Wahlkreisen. Die Aufgabe besteht darin, ein Gebiet in eine bestimmte Anzahl an Wahlkreisen aufzuteilen, sodass mehrere Anforderungen und Kriterien erfüllt werden, die durch das Gesetz und Rechtsprechungen vorgegeben sind. Die Terminologie "optimal" bedeutet hier eine bestmögliche Erfüllung der gesetzlichen Einteilungskriterien. Im Mittelpunkt der Arbeit steht die Problemvariante bei der deutschen Bundestagswahl. In Deutschland wird vor jeder Wahl eine Revision der Wahlkreise durchgeführt. Darüber hinaus wird das Thema derzeit im Rahmen einer Reform des Wahlrechts diskutiert. Der Beitrag dieser Dissertation umfasst eine ausführliche Darstellung der Lösungsmethoden, die in der Literatur vorgeschlagen werden, sowie verfügbare Software, die das Einteilen von Wahlkreisen unterstützt. Anschließend wird eine formale Definition der Problemstellung der Wahlkreiseinteilung präsentiert, die die deutschen Vorgaben berücksichtigt. Die entwickelte gemischt-ganzzahlige lineare Formulierung basiert auf einer neuartigen Bemessung von administrativer Konformität und Kontinuität. Beide Kriterien haben sich in der deutschen Praxis aus besonders wichtig erwiesen und sind in der Literatur noch nicht ausreichend berücksichtigt worden. Basierend auf dem Modell werden primale Heuristiken und exakte Preprocessing-Verfahren vorgestellt. Um eine praktische Anwendung der Methoden zu ermöglichen, ist die gesamte Forschung in ein einsatzbereites Entscheidungsunterstützungssystem integriert. Die Software basiert auf einem geografischen Informationssystem und beinhaltet detaillierte, aktuelle Daten. Abschließend dokumentiert die Dissertation, wie die entwickelte Software erfolgreich in der Praxis eingesetzt wurde. Im Auftrag des Bundeswahlleiters wurden optimierungsbasierte Wahlkreiseinteilungen berechnet, um eine parlamentarische Kommission bei den Bemühungen um eine Reform des Wahlrechts zu unterstützen.

Einrichtungen

  • Lehrstuhl für Operations Research [813310]