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)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2016

Abstract

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 final overview on the here presented results and with some final remarks.

Institutions

• Discrete Optimization Teaching and Research Unit [113320]
• Department of Mathematics [110000]