Optimisation des réseaux

Un réseau a une structure. Le problème de base consiste à définir la structure ou la topo- logie du réseau. Ceci revient à imposer des contraintes de connexité, voire de k-connexité. On peut également considérer des contraintes de diamètre pour imposer que les communications se fassent en un temps limité (voir [1], [5], [34], [35], [55], [77]). D’autres problèmes de to- pologie consistent à localiser des équipements d’un type particulier (concentrateurs, noeuds d’accès, etc) [81], [126]. Construire un réseau sous la forme d’un ensemble de réseaux d’accès connectés par une dorsale est un autre exemple de problème de topologie : comment faire ce découpage d’une manière optimale ?. Construire donc la topologie d’un réseau donne lieu à un ensemble de problèmes combinatoires très divers et souvent difficiles à résoudre. Tout devient plus complexe si on intègre un aspect dynamique de configuration des réseaux : des noeuds qui se déplacent ou qui changent de comportement induisant un changement de la topologie. Ré-optimiser la topologie en respectant un certain nombre de contraintes techniques est un challenge d’actualité.Une fois la topologie fixée, il faut relayer du trafic dans le réseau. En d’autres termes,il faut résoudre des problèmes de routage. Ceci se ramène souvent à des problèmes de flot dans un graphe. Plusieurs types de contraintes peuvent être prises en compte : routage de chaque demande sur un seul chemin [7], routage sur plus court chemin [8], [41], routage avec contraintes de délai [6], routage avec contrainte d’équité [105]. On peut également considérer des contraintes de sécurisation se traduisant par l’obligation de rerouter le trafic en cas de panne de certaines composantes du réseau [10], [91], [99]. Tous ces problèmes de routage peuvent aussi être étudiés dans un contexte incertain, c’est à dire lorsque la matrice de trafic qu’on cherche à écouler dans le réseau n’est pas définie d’une manière précise. On peut par exemple supposer que la matrice de trafic varie dans un polytope et chercher un routage compatible avec toutes ces matrices [9], [107], [114].

Pour router du trafic sur une topologie déterminée, il faut installer des capacités de transmis- sion. Ces capacités sont souvent choisies parmi un ensemble discret. L’optimisation du coût des capacités installées se ramène souvent à un problème de programmation linéaire en nombres entiers. Ces problèmes sont généralement appelés problèmes de dimensionnement. Ils sont en réalité souvent résolus en même temps que les problèmes de routage. Un autre type de problèmes d’optimisation qui se posent dans le contexte des réseaux est le problème de tarification. En effet, un réseau offre des services qui doivent être facturés aux clients. Trouver le bon mode de tarification qui garantit par exemple une certaine équité ou un certain niveau de bénéfice à l’opérateur, se ramène à des problèmes d’optimisation et de théorie des jeux [16]. sont linéairement indépendants (respectivement. affinement indépendants) si on ne trouve pas de vecteur qui s’exprime en combinaison linéaire (combinaison affine) des autres vecteurs. Si S est un ensemble de vecteurs d’incidence dans R En utilisant cette notation, on peut alors formuler un problème d’optimisation combinatoire, en un programme en 0-1. Considérons maintenant l’enveloppe convexe de tous les vecteurs d’inci- dence. Si on dispose d’une description polyèdrale de cette enveloppe convexe, alors maximiser la fonction linéaire wx sur cet ensemble est strictement équivalent à la maximiser sur l’ensemble des vecteurs d’incidence. On sait, en effet, que tout programme linéaire atteint son optimum en au moins un point extrême. La difficulté de cette approche réside dans la caractérisation polyèdrale de l’enveloppe convexe. Notons qu’en pratique, une description partielle pourrait suffir lorsqu’on applique une méthode du type Branch&Cut qu’on décrira dans la suite.

Il est difficile de décrire l’ensemble des facettes de l’enveloppe convexe des solutions réa- lisables d’un problème combinatoire NP-Difficile. Ceci est une conséquence de l’équivalence entre la séparation et l’optimisation. Cependant, même si le problème combinatoire est facile à résoudre, il peut être difficile d’énumérer toutes les facettes. En effet, dans certains cas, elles sont en nombre exponentiel. Dans d’autres cas, on ne connaît même pas la forme de ces fa- cettes. Pour un problème d’optimisation combinatoire donné, il est en général difficile de carac- tériser le polyèdre associé par un système d’inégalités linéaires. De plus, même si ce dernier est caractérisé, le système décrivant le polyèdre peut contenir un nombre exponentiel d’inégali- tés et donc reste inexploitable pour être résolu comme un programme linéaire. Cependant, une description partielle du polyèdre garantie par la méthode de coupes peut être suffisante pour résoudre le problème jusqu’à l’optimum.