L’Ecole doctorale : Ecole Doctorale de l’Institut Polytechnique de Paris
et le Laboratoire de recherche SAMOVAR – Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux
présentent
l’AVIS DE SOUTENANCE de Monsieur Yacine AL NAJJAR
Autorisé à présenter ses travaux en vue de l’obtention du Doctorat de l’Institut Polytechnique de Paris, préparé à Télécom SudParis en :
Mathématiques et Informatique
« Optimisation robuste adaptative pour la gestion du trafic dans les réseaux »
le MERCREDI 9 NOVEMBRE 2022 à 10h00
Salle 4A101
19 PLACE MARGUERITE PEREY, 91120 PALAISEAU
Membres du jury :
M. Walid BEN-AMEUR, Professeur, Télécom SudParis, FRANCE – Directeur de thèse
M. Arie KOSTER, Professeur, RWTH Aachen University en Allemagne – Rapporteur
Mme Joanna TOMASIK, Professeure, Centrale Supélec, FRANCE – Rapporteure
M. Adam OUOROU , Directeur de recherche, Orange Labs, FRANCE – Examinateur
M. Michael POSS, Directeur de recherche, Chercheur CNRS au LIRMM, FRANCE – Examinateur
M. Olver NEIL, Associate Professor, London School of Economics and Political Science, ROYAUME-UNI – Examinateur
M. Jérémie LEGUAY, Chargé de recherche, Huawei Technologies France , FRANCE – Co-encadrant de thèqse
Résumé :
Étant donnée la nature dynamique du trafic, nous étudions la variante du problème de dimensionnement robuste de réseaux qui consiste à déterminer la capacité à réserver sur chaque lien d’un réseau de telle sorte que chaque demande appartenant à un polytope donné puisse être routée. L’objectif est soit de minimiser la congestion soit un coût linéaire. Nous étudions tout d’abord l’approximabilité de la variante avec un routage fractionnaire et dynamique dans des graphes non dirigés. Nous prouvons tout d’abord que, sauf si $P=NP$ le problème de minimisation de la congestion ne peut être approché en dessous d’aucun facteur constant répondant ainsi à une question ouverte de Chekuri (2007). Ensuite, en utilisant la conjecture ETH, nous prouverons une borne inférieure de $Omega(log n / log log n )$ sur l’approximabilité de ce problème. Nous portons ensuite notre attention sur la variante avec un graphe dirigé. Nous montrons qu’une solution avec un routage statique optimal donne une $O(sqrt{k}) = O(n)$-approximation du routage dynamique optimal, où $k$ est le nombre de commodités et $n$ le nombre de noeuds. Nous montrons ensuite qu’une généralisation naturelle du problème ne peut être approché en dessous d’un facteur de $k^{frac{ c }{ log log k }}$ pour une certaine constante $c$ (resp. $2^{log^{1- epsilon} k }$ pour tout $epsilon > 0$) sauf si $NP subseteq SUBEXP$ (resp. $NP subseteq QP$). Nous étudions également plusieurs reformulations du problème de dimensionnement robuste de réseaux permettant d’améliorer la méthode de routage affine. Nous montrons tout d’abord que la formulation par noeud-arc peut être moins restrictive que la formulation par arc-chemin. Nous fournissons également une formulation naturelle équivalente a la formulation par noeud-arc. Nous étudions ensuite plusieurs formulations basées sur des relaxations des contraintes de conservation de flot. Ensuite, nous étudions des formulations basées sur des agrégations de commodité par source ou par destination. Enfin nous proposons une stratégie intermédiaire entre l’approche statique et l’approche dynamique pour s’approcher encore plus du dynamique tout en contrôlant la complexité. Il s’agit d’une approche qu’on pourrait qualifier de multi-statique. L’idée est de choisir un ensemble de faces du polytope représentant l’ensemble d’incertitude de telle manière que l’union des ces faces contienne tous les points extrêmes non-dominés de cet ensemble. Un routage statique est considéré pour chacune de ces faces.
Abstract : « Adaptive Robust Optimization for Network and Traffic Management »
Given the dynamic nature of traffic, we investigate the robust network design problem where we have to determine the capacity to reserve on each link so that each demand vector belonging to a polyhedral set can be routed. The objective is either to minimize congestion or a linear cost. When routing is assumed to be fractional and dynamic (i.e., dependent on the current traffic vector), we first prove that the robust network design problem with minimum congestion cannot be approximated within any constant factor, settling an open question by Chekuri (2007). Then, using the ETH conjecture, we get a $Omega(frac{log n}{log log n})$ lower bound for the approximability of this problem. We next focus on the variant in which the underlying graph is directed. We prove that an $O(sqrt{k}) = O(n)$-approximation can be obtained by solving the problem under static routing, where $k$ is the number of commodities and $n$ is the number of nodes. We show that a natural generalization of the problem cannot be approximated within a ratio of $k^{frac{ c }{ log log k }} $ for some constant $c$ (resp. $2^{log^{1- epsilon} k }$ for any $epsilon >0$) unless $NP subseteq SUBEXP$ (resp. $NP subseteq QP$). Affine routing can be used to obtain better solutions also with polynomial-time algorithms. It consists in restricting the routing to depend on the demands in an affine way. We first show that a node-arc formulation is less conservative than an arc-path formulation. We also provide a natural cycle-based formulation that is shown to be equivalent to the node-arc formulation. To further reduce the solution’s cost, several new formulations are proposed. They are based on the relaxation of flow conservation constraints. The obtained formulations have been further improved through aggregation. As might be expected, aggregation allows us to reduce the size of formulations. A more striking result is that aggregation reduces the solution’s cost. We finally propose an intermediate strategy between static and dynamic routing that can be seen as a new variant of multi-static routing. We consider some faces of the uncertainty set whose union contains all non-dominated extreme points of the polytope. Then a static routing is considered for each of these faces.