Fixed charge network design problem with user-optimal flows

Conception de réseaux avec flots optimaux pour les usagers Cette thèse s'adresse à la classe des problèmes de conception de réseaux bi-niveaux. Nous nous sommes intéressés à l'étude des applications des différents domaines et au développement d'algorithmes exacts pour la résolution des problème de réseaux bi-niveau correspondants. En particulier, nous avons étudié le problème de conception de réseau bi-niveau dans lequel le ``leader" sélectionne une partie du réseau à activer, puis, dans le deuxième niveau, la solution doit être optimale pour un problème de flot dans le sous-réseau sélectionné. Dans cette thèse, trois applications de ce problème sont étudiées : le transport de matières dangereuses, les réseaux de télécommunication et les réseaux sociaux. Le problème de deuxième niveau dans la première et la dernière application est un problème de plus court chemin alors qu'un flot de coûts minimum est requis dans la deuxième application.Le premier problème étudié est le problème de conception de réseau avec coût fixe avec contraintes de plus court chemin. Le problème est modélisé comme un programme bi-niveaux qui peut être appliqué dans le transport des matières dangereuses. Pour ce problème, nous proposons deux nouvelles formulations de programmation en nombres entiers (PLNE) inspirées par des inégalités de chemin et de cycle. Nous incorporons ces formulations dans des algorithmes de branch-and-cut et de plans coupants. Des tests numériques sont effectués sur des instances réelles et sur un ensembles d'instances aléatoires qui sont générées avec différents critères pour examiner la difficulté de ces instances. Les résultats montrent que les algorithmes de plan coupants proposés peuvent résoudre jusqu’à 19% d’instances de plus que les formulations compactes.Le deuxième problème étudié concerne la gestion de la consommation d'énergie dans les réseaux de télécommunication en utilisant un protocole de routage multi-chemins pour minimiser la capacité des liens utilisée. Nous proposons un modèle d'optimisation bi-niveaux dans lequel le premier niveau représente la fonction de gestion de l'énergie et le deuxième est un protocole de routage multi-chemins. Ensuite, le problème est reformulé par des formulations PLNE en remplaçant le problème du deuxième niveau par ses conditions d'optimalité. Ces formulations sont utilisées pour résoudre le problème avec les algorithmes classiques de plans coupants et de branch-and-cut. Les expérimentations sont effectuées sur des instances réelles afin de comparer les algorithmes proposés et d'évaluer l'efficacité de notre modèle par rapport aux modèles existants à un seul chemin et de multi-objectifs.Enfin, nous étudions le problème de la maximisation d’influence dans les réseaux sociaux signés. A notre connaissance, c'est la première fois que ce problème est considéré comme un problème de programmation à deux niveaux. Nous reformulons le problème en modèles PLNE à un niveau en utilisant trois différentes conditions d'optimalité du problème de plus court chemin apparaissant dans le deuxième niveau. Ces formulations sont renforcées en ajoutant un ensemble d'inégalités valides. Des tests numériques sont effectués sur des instances aléatoires pour comparer les différentes formulations proposées. Enfin, des solutions optimales en temps polynomial sont proposées pour des cas particuliers des graphes.