Modèles et Algorithmes pour le Problème d’Interdiction de l’Arbre Couvrant de Poids Minimal

Abstract

Dans cette thèse, nous étudions le problème de l’Interdiction de l’Arbre Couvrant Minimal (IACM). Ce problème estun jeu à deux joueurs entre un opérateur de réseau et un interdicteur. Le premier détermine un Arbre CouvrantMinimal (ACM) dans un réseau. Limit ´e par un budget, le second cherche `a changer la topologie du réseau pouraugmenter le poids de l’ACM. Deux types d’interdiction sont considérés : l’interdiction totale et l’interdiction partielle.Une arête totalement interdite est considérée comme absente tandis que le poids d’une arête partiellement interditeest augmentée d’une quantité prédéfinie. Le budget de l’interdicteur est modélisé par une contrainte de cardinalité,chaque arête a le même poids d’interdiction, ou une contrainte de sac `a dos, les poids d’interdiction peuvent êtredifférents. Sept formulations mathématiques du problème IACM ont été élaborées. Elles se sont avérées efficacespour des graphes de petite et moyenne taille. Un algorithme de type ”Branch-and-Price” et un algorithme basé surla d´ecomposition de Benders ont ´ et ´e conc¸us pour les graphes de plus grande taille. En outre, des in ´ egalites validessont propos´ees pour renforcer les mod`eles et am´ eliorer les performances des algorithmes. Des instances de 200sommets et 19900 ar ˆetes ont ainsi pu ˆ etre r ´esolues optimalement.