Algorithmische Behandlung schwerer Optimierungsprobleme in Netzwerken

点击翻译按钮获取中文摘要

Ein zentrales Problem in Netzwerken besteht darin, Verbindungsstrukturen zu finden, die gewisse Kriterien erfüllen. Der Kern dieses Problems wird durch das Steiner-Problem in Netzwerken modelliert, also das Problem, eine gegebene Menge von Knoten in einem gewichteten Graphen möglichst kostengünstig zu verbinden. Aufbauend auf der erfolgreichen Arbeit über das Steiner-Problem werden in dem Projekt folgende Ziele verfolgt: 1. Vertiefung des strukturellen Wissens über das Steiner-Problem, seine Relaxationen und die damit verbundenen Bearbeitungsmethoden, 2. Entwicklung eines auf Interior-Point Methoden basierenden Algorithmus für große Instanzen des Steiner-Problems. Diese Zusammenführung von Fortschritten bei Linearer und Kombinatorischer Optimierung stellt eine methodische Innovation dar, die zudem die Möglichkeit einer effizienten verteilten (parallelen) Implementierung beinhaltet. 3. Adaption der beim Steiner-Problem erfolgreichen Methoden auf verwandte schwere Optimierungsprobleme, insbesondere die durch die Anwendungen motivierten Mehrkriterienprobleme wie gradbeschränkte Steiner- und Spannbäume.