ISBN 9783843947985

978-3-8439-4798-5, Reihe Mathematik

Pascal Halffmann
Advances in Multiobjective Optimisation: Scalarisation, Approximation, and Complexity

383 Seiten, Dissertation Technische Universität Kaiserslautern (2021), Hardcover, A5

Zusammenfassung / Abstract

Viele reale Entscheidungsprobleme erfordern die Berücksichtigung von mehreren, oft gegenläufigen Zielfunktionen, die simultan optimiert werden. Diese Art von Problemen mit mehreren Optimallösungen werden in der multikriteriellen Optimierung untersucht. Obwohl eine Vielzahl von Anwendungsmöglichkeiten existiert, ist die Forschung in diesem Bereich noch relativ am Anfang. In dieser Arbeit werden wir die Forschung in diesem Teilgebiet der Optimierung vorantreiben. Hierbei fokussieren wir uns auf (gemischt-)ganzzahlige lineare Probleme und drei besondere Themen, Skalarisierungsmethoden, Approximation und Komplexitätstheorie. Dabei beantworten wir offene Forschungsfragen und beschreiten neue Forschungsrichtungen, die uns ein neues Verständnis von multikriteriellen Problemen bieten.

Wir verallgemeinern das Konzept der gewichteten Summe Skalarisierung, indem wir hier auch Zielfunktionen gewichtet aufsummieren aber damit ein niedrigdimensionales multikriterielles Problem erzeugen und erarbeiten fundamentale Eigenschaften. Basierend auf der gewichteten Summe, entwerfen wir einen Approximationsalgorithmus für bikriterielle und parametrische ganzzahlige Probleme. Für die Gewichtsmengenzerlegung der gewichtete Summe Methode konstruieren wir den aktuell schnellsten Algorithmus, der die Gewichtsraumzerlegung bestimmt. Außerdem entwickeln wir Approximationsalgorithmen mit polynomieller Laufzeit für Komponenten der Gewichtsraumzerlegung. Ferner wenden wir zum ersten Mal die Gewichtsmengenzerlegung auf die gewichtete Tchebycheff Skalarisierung an und gewinnen fundamentale Eigenschaften des Gewichtsraums sowie innovative Lösungsmethoden. Hinzu stellen wir eine Kategorisierung kombinatorischer Probleme bezüglich ihrer Komplexität bereit.Diese Forschungsbeiträge werden ergänzt durch einen Überblick der

verfügbaren Lösungsmethoden für multikriterielle Problenme sowie einem detaillierten Blick auf zukünftige Forschungsmöglichkeiten.