Abstract FR:

Nous étudions le problème de la conception de réseaux de télécommunications multiprotocoles tenant compte du phénomène d'encaspulation des données. Connaissant la structure en couches d'un réseau multiprotocoles et un ensemble de demandes devant être acheminées sur ce réseau, le problème de la conception de réseau consiste à choisir la capacité de chaque liaison parmi un ensemble de valeurs discrètes de telle sorte que le coût global du réseau soit le plus faible possible, tout en s'assurant que les demandes sont satisfaites. Nous scindons ce problème en deux sous-problèmes inter-dépendants : le problème de la réalisabilité d'un ensemble de capacités en regard d'un multiflot, qui peut être formulé comme un programe linéaire en variables inconnues, et le problème du dimensionnement de ces capacités, formulé comme un programme linéaire en variables bolléennes. Dans le cadre des réseaux multiprotocoles, le problème de la réalisabilité d'un ensemble de capacités en regard d'un multiflot fait intervenir la notion d'en-tête liée au phénomène d'encaspulation, ce qui rend sa résolution difficile. Nous introduisons dans cette thèse un modèle de multiflot dit non conservatif, et définissons la notion de pile de chemins. Nous étudions la complexité du problème de la recherche de piles de chemins comportant un nombre minimum de changements de protocoles dans les réseaux en couches. Nous donnons aussi un ensemble d'heuritiques pour la génération de piles de chemins de coût réduit négatif afin de résoudre le problème de réalisibilité. Le problème de dimensionnement des capacités peut être entièrement résolu de manière itérative en employant la classe des inégalités métriques. Par ailleurs, la formulation de ce problème faisant intervenir uniquement des variables booléennes, nous faisons appel à la technique dite lift-and-project due aux travaux de Lovasz et Schrijver sur le cône des matrices semi-définies positives, ainsi qu'aux travaux de Balas, Ceria, Cornuejols sur le rôle des contraintes disjonctives pour la résolution de programmes en variables booléennes. Nous étudions chacune de ces approches et donnons deux algorithmes de coupes polyédrales basés sur l'utilisation des opérateurs de projection définis par Lovasz et Schrijver d'une part, et Balas, Ceria, Cornuejols. Enfin nous donnons une méthode permettant de créer plusieurs relaxations semi-définies d'un programme linéaire en variables booléennes général, et nous appliquons une méthode au problème de dimensionnement des capacités. Des tests numériques permettent de dire que les solutions obtenues par cette méthode sont meilleures que celles obtenues par la simple relaxation linéaire de ce problème