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

Tieves, Martin; Koster, Arie Marinus; Amaldi, Edoardo

doi:HT019214496

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

2016 & 2017

Verantwortlichkeitsangabevorgelegt von Master of Science RWTH Aachen University Martin Tieves

ImpressumAachen 2016

Umfang1 Online-Ressource (xi, 220 Seiten) : Diagramme, 1 Karte

Dissertation, RWTH Aachen University, 2016

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2017

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Koster, Arie Marinus (Thesis advisor)^RWTH* ; Amaldi, Edoardo (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2016-12-16

Online
URN: urn:nbn:de:hbz:82-rwth-2017-007244
DOI: 10.18154/RWTH-2017-00724
URL: https://publications.rwth-aachen.de/record/682215/files/682215.pdf
URL: https://publications.rwth-aachen.de/record/682215/files/682215.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
optimization (frei) ; mixed integer linear progamming (frei) ; network design (frei) ; virtual network embedding (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Den Schwerpunkt der hier vorliegenden Dissertation bildet die mathematische Untersuchung zweier Optimierungsprobleme aus dem Telekommunikationssektor. Das Erste betriﬀt 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 ﬁnalen Bemerkungen.

In this thesis, we study two optimization problems, the Network Design Problem with Compression (NDPC) and the Virtual Network Embedding Problem (VNE). In both cases, our interest into the topic is motivated by the importance of these problems within the telecommunication industry, where they arise in the context of introducing new services and technologies.Throughout this work, we employ concepts and methods from the area of mathematical, respectively combinatorial, optimization. We aim to provide new insights, both from a theoretical and from a practical point of view. For that purpose, we carry out extensive computational experiments to strengthen our theoretical results. Wherever possible, we put our results into context with the existing literature.We follow a similar line of thought for both problems. For the NDPC problem, we present a mixed integer linear programming (MILP) formulation, detailed polyhedral investigations, and considerations on the problems computational complexity as well as a discussion on the problem under data uncertainty. We conclude our work on NDPC by computational results and an outlook into further research directions.For the VNE problem, we also start with an MILP formulation. We discuss heuristic problem approaches and investigate the problem’s computational complexity in great detail. We consider the VNE problem with data uncertainty and develop exact and heuristic solution approaches for this case. As for the NDPC problem, we present extensive computational experiments to evaluate our results. The chapter is closed by a short summary and a brief introduction to future research topics.We conclude this thesis by a ﬁnal overview on the here presented results and with some ﬁnal remarks.

OpenAccess:
PDF PDF (PDFA)
(additional files)