SPOC 24 "Optimisation combinatoire pour les réseaux de télécommunications"
Primary tabs
Date:
Thursday, 22 September, 2022
Inscription:
24ème séminaire du groupe POC
Le JEUDI 22 SEPTEMBRE 2022
En présentiel
Au laboratoire LAMSADE (Université Paris-Dauphine)
Place du Maréchal de Lattre de Tassigny 75017 PARIS
Salle A 709
Sur le thème
"Optimisation combinatoire pour les réseaux de télécommunications"
Séminaire organisé avec Huawei France, Nokia Bell Labs et Orange Labs
Entrée gratuite
Merci de vous inscrire à cette journée pour faciliter l'organisation
Pour voir la liste des inscrits
Programme de la journée:
9h45-10h45
From the Steiner Problem in Graphs to more complex network design problems
Eduardo UCHOA PUC-Rio, Brésil
The talk starts with the history of algorithms for the classic Steiner Problem in Graphs (SPG), from the first formulations to the recent advances in the thesis that just won the EURO Doctoral Dissertation Award. The accumulated advances in more than 40 years of research now allow the solution of typical instances with tenths of thousands of nodes and edges in less than one minute. A crucial point for that success is the fact that SPG admits a directed graph formulation. Then, it will be shown that many other network design problems that also admit directed formulations are now also well-solved. However, many more complex network design problems do not seem to admit directed formulations. The talk ends by presenting the distance-transformation technique for strengthening undirected formulations.
10h45-11h15 Pause
11h15-12h15
Combinatorial optimization in Huawei Datacom OR team
Sébastien MARTIN, Huawei France
The Datacom OR team of Huawei works on several Telecommunication network problems. In this talk, we focus on two main problems, hard slicing and IGP weight optimization. For hard slicing, the goal is to isolate users in a network thanks to a date plane technology where bandwidth is split over user dedicated time in slot. This problem is a particular network design problem, where the team tackles it with column generation and cutting plane methods. For the IGP weight optimization problem, it consists in finding a weight for each link such that demands are routed over shortest paths and the maximum link utilization is minimized. We present a method based on the Lagrangian relaxation to solve this problem. At the end, we give an overview of problems tackled by the team and the methods used to solve them.
12h15-14h00 Pause
14h00 - 15h00
Some recent contributions to the optimization of virtualized networks
Nancy Perrot Orange Labs
Network virtualization poses many challenges for infrastructure and service providers. Some of these challenges are related to network design, others are purely algorithmic, with the goal of providing decision-making tools to manage networks and end-to-end services efficiently. Given the large combinatorial nature of the decisions to be made, modeling and understanding the structure of global/optimal solutions is increasingly crucial to make strategic decisions for network evolution and derive some key decision procedures for network management. In this talk, I focus on two problems to illustrate these challenges and show, through recent studies that very promising results can be achieved by using finely tuned combinatorial optimization approaches.
15h00-15h30 Pause
15h30 - 16h00
Optimization and Resource Allocation for the Non-Orthogonal Multiple Access (NOMA)
Lou Salaün Nokia Bell Labs, France
Traditional practice of serving multiple users in a wireless communication system is often through orthogonal multiple access (OMA) scheme for simpler design, however it is known that OMA is in general sub-optimal and has several strict limitations. Drawing from recent advances and technology needs, we introduce the subject of non-orthogonal multiple access (NOMA) and present some interesting provable optimal and approximate algorithmic results, which allow to improve user service such as connectivity and resource utilization efficiency. We discuss the complex problem of joint subcarrier and power allocation (JSPA) under NOMA. To tackle this problem, we propose a generic optimization framework covering a large class of utility functions and practical constraints. In this framework, we divide the general JSPA problem into several subproblems and develop algorithms taking advantage of each subproblem’s specific properties. We also study their computational complexity and approximability. The generality and modularity of this framework allows to extend our algorithms to new constraints and scenarios.
16h00 - 16h30
Integer linear programming formulations for the maximum flow blocker problem
Isma Bentoumi Huawei France et Lamsade, Université, Paris Dauphine, France
Given a directed graph with capacities and interdiction costs associated with its arcs, we are interested in solving the maximum flow blocker problem (MFBP). The MFBP asks to find a minimum-cost subset of arcs to be removed from the graph in such a way that the remaining maximum-flow value does not exceed a given threshold. It has applications in telecommunication networks and in the monitoring of civil infrastructures, among others. We present two integer linear programming formulations for the MFBP which are used to derive the first exact algorithms to optimally solve the problem. The first formulation comes from the bilevel aspect of the MFBP. It has an exponential number of constraints and it is solved via a Branch-and-Cut algorithm. The second one has a polynomial number of variables and constraints and it is solved via a state-of-the-art ILP solver. This second formulation is obtained thanks to a relationship between the MFBP and the maximum flow interdiction problem. The two methods proposed are compared thanks to a computational campaign. Our tests aim at evaluating the performance of the exact algorithms and at determining the features of the instances which can be solved to proven optimality.