École Nationale Supérieure de
Techniques Avancées

Résumé

Dans ce stage, on s'est intéressé au problème de l'arbre de Steiner. Le problème de l'arbre de Steiner est un problème très classique de la théorie des graphes. Dans un graphe non-orienté pondéré G = (V,E) où ce représente le poids de l'arête e 2 E et connaissant un sous-ensemble de noeuds T _ V appelés terminaux, il s'agit de trouver l'arbre de poids minimum couvrant l'ensemble T. Le problème de l'arbre de Steiner a de nombreuses applications, notamment dans la conception de circuits integrés (VLSI) ou la conception de réseaux de télécommunications. Dans ce dernier cas, l'arbre de Steiner permet en e_et de réaliser à un coût minimal l'interconnexion de N usagers ou terminaux échangeant des informations via un service multicast. Le problème de l'arbre de Steiner est NP-complet dans le cas général et polynomial lorsque T = V ou |T| = 2 ou bien encore lorsque le graphe G est série-parallèle. Ce problème a déjà été considérablement étudié. Quelques articles récents dressent un bilan des formulations du problème de l'arbre de Steiner sous la forme de problèmes linéaires en nombres entiers. Dans ce stage, on s'est principalement intéressé à un article de Goemans et Muyng [1] qui compare ses di_erentes formulations en les projetant dans l'espace des variables naturelles du probleme, à savoir, l'espace R|E| dans lequel une variable binaire xe est associée à chaque arête. Parmi les nombreux résultats présentés dans [1], plusieurs montrent que de nombreuses formulations se projettent dans le même polyèdre Qx dans l'espace R|E|. En revanche, il n'y a pas ou peu de résultats concernant les autresformulations également proposées dans [1]. Dans ce rapport, plusieurs des résultats de [1] sont passés en revue avec des preuves détaillées, quelques autres formulations sont également proposées et d'autres polyèdres de R|E| sont mis enévidence. Les di_érentes formulations sont également testées numériquement et comparées surplusieurs instances de la Steinlib.