13ème Journée OR

La treizième journée thématique du groupe de travail "Optimisation dans les réseaux" du GDR-ROD organisée conjointement avec Orange Labs avec les supports du LIP6 et du LIMOS aura lieu le jeudi 10 et  vendredi 11 octobre 2024 dans les locaux du LIP6.

Thème de la journée : Optimisation dans les réseaux télécoms

Lieu : LIP6, salle 105 couloir 25-26

Campus Pierre et Marie Curie - Sorbonne Université

4 place Jussieu 75252 Paris Cedex 05

 L'inscription est gratuite mais obligatoire (voir l'onglet Register ci-dessus).

Programme prévisionnel de la journée du jeudi 10/10

9h-9h30 :   Accueil des participants (Café-croissant, distribution des badges, …)

9h30-10h30:   Benders decomposition for the discrete ordered median problem

Ivana Ljubic, ESSEC Business School of Paris
Ordered median optimization has been proven to be a powerful tool to generalize many well-known problems from the literature. In Location Theory, the Discrete Ordered Median Problem (DOMP) is a facility location problem where clients are first ranked according to their allocation cost to the nearest open facility, and then these costs are multiplied by a suitable weight vector l. That way, DOMP generalizes many well-known discrete location problems including p-median, p-center or centdian. In this article, we also allow negative entries of l, allowing us to derive models for better addressing equity and fairness in facility location, for modeling obnoxious facility location problems or for including other client preference models. We present new mixed integer programming models for DOMP along with algorithmic enhancements for solving the DOMP to optimality using mixed integer programming techniques. Specifically, starting from state-of-the-art formulations from the literature, we present several Benders decomposition reformulations applied to them. Using these approaches, new state-of-the-art results have been obtained for different ordered weighting vectors.
Based on a joint work with M.P. Pozo, J. Puerto and A. Torrejon:  Benders decomposition for the discrete ordered median problem, European Journal of Operational Research 317 (2024) 858–874

10h30 - 11h : Pause café

11h-11h30 :   Generalized Lagrangian method for nonlinear network optimization problems

 Dimitrios Papadimitriou, Université libre de Bruxelles

11h30-12h :    Modèles mathématiques avec contrainte d'arbre couvrant de poids minimum

Rafael Andrade, Université Fédérale de Ceará, Brésil

Nous verrons comment traiter les modèles mathématiques de la forme min{f(x,y)} soumis à x dans un ensemble X, où y est un arbre couvrant de poids minimum dépendant de x. Un exemple typique est le problème de l'arbre couvrant robuste avec critère de robustesse relative. Dans ce problème, les arêtes d’un graphe ont des coûts qui varient dans un intervalle donné. Dans un scénario de coût pour de telles arêtes basé sur ces intervalles de coûts, le poids d'un arbre couvrant T du graphe est la somme des coûts de ses arêtes dans ce scénario. Son écart de robustesse est défini comme la différence entre son poids et celui de l’arbre couvrant de poids minimum pour ce scénario. L'objectif du problème est de déterminer, parmi tous les arbres couvrants du graphe, celui qui minimise l'écart de robustesse maximum parmi tous les scénarios de coûts possibles pour les arêtes.

L'essentiel est de savoir comment décrire l'arbre couvrant de poids minimum y avec des inégalités linéaires dans l'ensemble de contraintes du problème !

Nous montrerons la théorie et les nouveaux concepts derrière la conception d'un tel ensemble d'inégalités linéaires dont les solutions faisables correspondent à des arbres couvrant de poids minimum. À cette occasion, nous abordons des questions théoriques ouvertes sur ce sujet.

12h-12h30 : A First Study of the Parameterized Complexity of Segment Routing

Camille Richer, Orange INNOV/DataAI

Segment Routing is a recent network technology that provides finer control over the routing paths. Instead of routing directly from a source to a target, packets are routed via intermediate waypoints. Between consecutive waypoints, the packets are routed according to the usual shortest path routing protocol. The associated traffic engineering problem is NP-hard: given a network topology and a set of demands, the task is to find for each demand at most k waypoints such that shortest path routing along these waypoints fulfills all demands and do not exceed the capacities of the network. 
In this talk, we provide a first analysis of this problem from a parameterized complexity point of view. We investigate if special structures of real-world communication networks could be exploited to design exact efficient algorithms. Our results exclude (under standard complexity assumptions) many such algorithms, but we find some polynomial-time solvable special cases.

12h30-14h :    Déjeuner offert au restaurant l’Ardoise (campus Jussieu)

14h-15h :    Robust optimization for the Segment Routing Traffic Engineering Problem

Bernard Fortz, HEC Liège et Université de Liège

Segment routing, a modern protocol enhancing traffic engineering, introduces flexibility by enabling traffic to take detours. This talk tackles the challenge of optimizing routing in the face of uncertain traffic distribution. Unlike traditional methods relying on a single traffic matrix, our approach considers an infinite set of matrices defined by linear constraints. Our goal is to optimize routing under the worst-case scenario within this set. Through innovative formulations, our results showcase a substantial speed improvement in optimization compared to traditional methods, offering an efficient alternative to exploring all extreme points in the matrix set.
This is joint work with Hugo Callebaut and Jérôme De Boeck

15h-15h30 :     Pause café

15h30-16h : Distributed Congestion Mitigation for Segment Routing

Sébastien Martin, Huawei Paris Research Center

In telecommunication networks based on Segment Routing, congestion can appear after a link failure or a traffic burst. When a router detects congestion on an outgoing link, a tactical policy is deployed to reroute traffic on alternative paths to mitigate congestion locally. In this talk, three challenges are considered: computation of alternative paths, monitoring of available bandwidth capacity, and dynamic split of traffic over these alternative paths. The proposed solutions are mainly based on Integer Linear Programming.

16h-16h30:     Multi-Commodity Flow problem with Convex Costs

Guillaume BERAUD-SUDREAU (Huawei - LIMOS)

Programme prévisionnel de la journée du vendredi 11/10

9h-9h30 :   Accueil des participants (Café-croissant, distribution des badges, …)

9h30-10h15:   Les réseaux optiques: des premiers systèmes WDM aux réseaux flexibles

Michel Morvan, IMT Atlantique

Ce tutoriel se propose de revisiter les principes architecturaux des réseaux optiques, depuis leur genèse au début des années 90 jusqu'aux  dernières avancées technologiques. Les différents mécanismes de protection et de résilience aux pannes seront notamment décrits et leurs conséquences sur les architectures expliquées. Enfin, nous reviendrons sur les choix techniques initiaux qui continuent de conditionner le dimensionnement de tels réseaux.

10h15-10h45 :     Pause café

10h45-11h45:   GNPY : a game changer software for the design of optical transport networks

Esther Le Rouzic, Orange Labs

Orange operates national optical networks for voice and data traffic, relying on proprietary design tools that create supplier dependency. GNPy, an open-source tool developed by a community of academics and operators, addresses this by integrating public models for collaboration and enabling comparisons between suppliers. Its agnostic nature allows modeling with various equipment and promotes the development of open, standardized APIs for automating optical transport networks.

11h45-12h15:   Integrating Quality of Transmission Constraints in Optical Networks Optimization

Pedro Henrique Fernandes Da Silva, IMT Atlantique; LIMOS

12h15-12h45:   Network Reconfigurations in Elastic Optical Networks: Literature Review and Research Opportunities

Rafael Colares, LIMOS, Université Clermont Auvergne

12h45:   Clôture des journées et déjeuner offert au restaurant Ardoise (campus Jussieu)