Le problème de l'arbre couvrant budgété : Formulations étendues, Projection et Algorithme de coupes et branchements
11/06/2025 à 11h00
M. Charles NOURRY présente ses travaux en soutenance le 11/06/2025 à 11h00
À l'adresse suivante : Université Paris Dauphine - PSL- Place du Maréchal de Lattre de Tassigny 75016 Paris - Salle des thèses - D 520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Le problème de l'arbre couvrant budgété : Formulations étendues, Projection et Algorithme de coupes et branchements
É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
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Ali Ridha MAHJOUB | Professeur émérite | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| M. François CLAUTIAUX | Professeur | INSTITUT DE MATHEMATIQUES DE BORDEAUX | Rapporteur |
| M. Frédéric MEUNIER Professeur | Professeur | ECOLE NATIONALE DES PONTS ET CHAUSSEES, CERMICS | Rapporteur |
| M. Hassène AISSI | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Co-encadrant de thèse |
| M. Adam N. LETCHFORD | Professor | LANCASTER UNIVERSITY | Examinateur |
| M. Mourad BAIOU | Directeur de recherche | UNIVERSITE CLERMONT AUVERGNE | Examinateur |
| Mme Hande YAMAN PATERNOTTE | Full professor | FACULTY OF ECONOMICS AND BUSINESS | Examinatrice |
| M. Matthieu CHARDY | Ingénieur de recherche | ORANGE LABS | Examinateur |
Résumé
Le problème de l’arbre couvrant d-budgété combine les structures de l’arbre couvrant et du sac à dos multiple. On retrouve ce problème dans de nombreuses applications, notamment dans le domaine de la conception de réseaux. Les différentes contraintes de budget permettent de prendre en compte plusieurs critères, potentiellement conflictuels, que l’on retrouve dans de nombreux problèmes réels. Nous considérons des algorithmes exacts, basés sur une approche polyédrale, pour résoudre le problème de l’arbre couvrant budgété avec une ou plusieurs contraintes de budget. Dans le cas où d = 1, nous présentons une formulation étendue exacte basée sur des intersections de matroïdes et la programmation disjonctive. En raison de la NP-difficulté du problème, cette formulation est exponentiellement grande et ne peut être résolue ou projetée telle quelle. Nous exploitons donc la structure du cone de projection afin de sélectionner des rayons qui combinent les polytopes de l’arbre couvrant et du sac à dos. Nous intégrons cette technique de projection ainsi que plusieurs routines de séparation efficaces dans un algorithme de coupes et de branchements, et les résultats expérimentaux montrent que notre procédure domine les algorithmes de l’état de l’art. Nous généralisons notre algorithme pour résoudre le problème avec d > 1 contraintes de budget.