Abstract

Telecommunication companies use software with heuristic algorithms to plan their routing. However, with network demands increasing at such a rapid pace, the effectiveness of these heuristics becomes a critical issue.
Therefore, our research focuses on designing large-scale optimization models and algorithms for solving provisioning problems in 5G networks. Our works can be categorized into two main topics: provisioning problems at the physical layer and provisioning problems at the logical layer.


The first topic of the thesis focuses on the Routing and Spectrum Assignment (RSA) problem and is structured into three parts. In the first part, we propose a new decomposition exact modeling of the RSA problem, based on a link decomposition, in order to further improve the scalability of previous exact methods. Solution requires a column generation (CG) algorithm, a powerful decomposition technique, to derive proven epsilon-optimal solutions, with small epsilon values.


The second part presents a decomposition model that still aimed at maximizing throughput in the RSA problem, but subject to additional interference (also called. Optical Signal-to-Noise Ratio (OSNR)) constraints using the Gaussian Noise (GN) model. It is built upon the link-based decomposition model from the first part. The solution combines a Tabu Search (TS) to handle non-linear components within a Column Generation algorithm.


In the third part, we address the limitations observed in the second part, specifically the suboptimal solution of subproblems resulting from using TS. To overcome this, we propose a reformulation of the subproblems as Maximum Weight Independent Set (MWIS) problems to more effectively handle the non-linearities, and improve on both the scalability and the accuracy of the solutions.


The second topic addresses the challenge of ensuring protection for Service Function Chaining (SFC) requests in an Open Radio Access Network (O-RAN). We investigate two protection schemes (dedicated vs. shared) and two distinct objective functions (availability vs. latency), which both require handling non-linearities in an efficient manner in order to remain with scalable exact solution schemes.