Discrete and robust optimization approaches to network design with compression and virtual network embedding

• Diskrete und robuste Optimierungsansätze zum Netzwerkdesign-Problem mit Komprimierung und zur Einbettung virtueller Netze

Tieves, Martin; Koster, Arie Marinus (Thesis advisor); Amaldi, Edoardo (Thesis advisor)

Aachen (2016, 2017)
Doktorarbeit

Dissertation, RWTH Aachen University, 2016

Kurzfassung

Den Schwerpunkt der hier vorliegenden Dissertation bildet die mathematische Untersuchung zweier Optimierungsprobleme aus dem Telekommunikationssektor. Das Erste betrifft die Dimensionierung von Kommunikationsnetzen wenn die Möglichkeit besteht Datenströme zu komprimieren (NDPC). Das Zweite entsteht bei der Einbettung von virtuellen Kommunikationsnetzen in gegebene Substrat-Netzwerke (VNE). Beide Probleme sind insbesondere für die Telekommunikationsindustrie relevant. Unter anderem treten sie dort bei der Betrachtung von Technologien zur Einführung neuer Dienstleistungen beziehungsweise von Serviceverbesserungen auf.In dieser Arbeit verwenden wir hauptsächlich die Methoden und Konzepte der mathematischen beziehungsweise der kombinatorischen Optimierung. Das Ziel dieser Arbeit ist es neue Einsichten in die Thematik sowohl aus praktischer als auch aus theoretischer Perspektive zu erarbeiten. Wir präsentieren ausführliche Rechenstudien um unsere theoretischen Ergebnisse zu unterstützen. Wenn immer es möglich ist ordnen wir unsere Resultate in den Kontext der bereits existierenden Literatur ein.Für beide Probleme verfolgen wir einen ähnlichen Ansatz. Für das NDPC Problem präsentieren wir eine Formulierung als gemischt ganzzahliges, lineares Programm (MILP), detaillierte Untersuchungen bezüglich des davon induzieren Polyeders und Betrachtungen zur Berechnungskomplexität sowie zur Unsicherheit von Eingabedaten. Wir schließen dieses Kapitel mit einer Diskussion unserer Rechenstudien ab und geben eine kurze Zusammenfassung der zum NDPC erzielten Resultate sowie einen Ausblick auf weitere Forschungsmöglichkeiten.Auch für das VNE Problem untersuchen wir zunächst eine Formulierung als MILP. Im Folgenden diskutieren wir heuristische Lösungsansätze und untersuchen die Berechnungskomplexität des VNE Problems. Wir betrachten das VNE Problem unter Datenunsicherheit und entwickeln exakte und heuristische Lösungsverfahren für diesen Fall. Wie für das NDPC Problem diskutieren wir zuletzt die Ergebnisse unserer Rechenstudien und geben einige Bemerkungen über potentielle zukünftige Forschungsrichtungen.Wir schließen diese Dissertation mit einer Zusammenfassung unserer Ergebnisse sowie mit einigen finalen Bemerkungen.

Einrichtungen

• Lehr- und Forschungsgebiet Diskrete Optimierung [113320]
• Fachgruppe Mathematik [110000]