Étude du problème de bloqueur appliqué aux multiflots : analyse polyédrale et algorithmes
08/07/2024 à 14h00
Mme Isma BENTOUMI présente ses travaux en soutenance le 08/07/2024 à 14h00
À l'adresse suivante : Université PARIS DAUPHINE PSL, Place du Maréchal de Lattre de Tassigny, 75016 Paris, France Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Étude du problème de bloqueur appliqué aux multiflots : analyse polyédrale et algorithmes
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. Ali Ridha MAHJOUB, M. Fabio FURINI
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Ali Ridha MAHJOUB | Professeur émérite | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| M. Fabio FURINI | Full professor | Sapienza University of Rome | Co-directeur de thèse |
| Mme Ivana LJUBIC | Full professor | ESSEC Business School France | Rapporteure |
| M. Alain QUILLIOT | Professeur émérite | Université Clermont-Auvergne | Rapporteur |
| M. Sébastien MARTIN | Maître de conférences | Huawei Technologies France | Co-encadrant de thèse |
| M. Roland GRAPPE | Professeur des universités | Université PARIS DAUPHINE PSL | Examinateur |
| Mme Nancy PERROT | Ingénieur de recherche | Orange Labs France | Examinatrice |
| Mme Fatiha BENDALI | Professeur | Université Clermont Auvergne | Examinatrice |
| M. Ibrahima DIARRASSOUBA | Maître de conférences | Université le Havre Normandie | Invité |
Résumé
Les réseaux de télécommunication sont des systèmes complexes dans lesquels s'inscrivent des problèmes d'optimisation combinatoire difficiles. Face à une demande croissante, l'efficacité de ces réseaux devient cruciale, notamment en termes de délai et de résilience face aux anomalies. Cette thèse se concentre sur l'analyse de la résilience des réseaux, avec pour objectif principal de déterminer le nombre maximal d'anomalies que le réseau peut supporter tout en maintenant sa fonctionnalité selon des critères spécifiques. Ce défi relève d'une classe de problèmes d'optimisation connus sous le nom de problèmes de bloqueur sur les flots. Notre travail se focalise particulièrement sur les problèmes de multiflots rencontrés dans les réseaux de télécommunication, caractérisés par des contraintes complexes de satisfaction des demandes. Nous nous intéressons aux demandes ayant différentes formes de trafic et prédites avec des méthodes d'apprentissage automatique. Le problème étudié est appelé problème de bloqueur sur les multiflots. Pour répondre à cette problématique, nous utilisons des outils d'optimisation combinatoire, explorant diverses approches, y compris les techniques bi-niveau, l'approche polyèdrale et les algorithmes de branchement. Nous abordons initialement le problème du bloqueur sur le flot maximal. Pour le résoudre, nous proposons plusieurs formulations de programmation linéaire entière, ainsi qu'une technique dérivée d'un résultat théorique établissant un lien structurel avec un problème existant dans la littérature. Par la suite, nous étendons notre travail pour traiter la notion de bloqueur sur les multiflots, en couvrant plusieurs variantes. Pour ce faire, nous introduisons une formulation avec une famille exponentielle de contraintes, résolue à l'aide d'un algorithme de branchement et de coupes. De plus, nous développons une approche polyèdrale pour renforcer la robustesse du modèle. Les performances des méthodes exactes proposées pour résoudre les deux problèmes décrits sont évaluées à travers une étude expérimentale approfondie.