Construire une formulation mathématique des contraintes d’uni-cyclicité

La structure faciale de P(G, p)

Ce problème a des applications dans les réseaux de télécommunications. En effet, on sou- haite en général construire un réseau de coût total minimum avec un certain niveau de résistance aux pannes. La structure du cycle (ou l’anneau dans le contexte des réseaux) est une bonne alternative pour apporter une certaine résistance aux pannes simples de liens. Les demandes en trafic entre des nœuds d’un même cycle sont protégées contre ces éventuelles pannes alors que les autres demandes peuvent être interrompues. Cependant, des cycles de petites tailles n’offrent qu’une protection limitée, d’où la considération d’une contrainte sur la taille des cycles. D’autres contraintes peuvent aussi être importantes à considerer (la taille des com- posantes connexes, le nombre des composantes connexes, des contraintes sur les degrés des noeuds, etc. L’objet de ce chapitre est l’étude du problème de synthèse des réseaux à composantes connexes unicycliques respectant une contrainte sur la taille des cycles. Le réseau ne doit pas contenir des cycles d’une taille inférieure ou égale à p. L’étude proposée est polyèdrale.

Nous présentons donc un ensemble d’inégalités valides dont nous étudions la dimension des faces induites ainsi que leurs algorithmes de séparation. Des résultats numériques montrent que l’ap- proche permet de résoudre des problèmes pratiques de dimensions raisonnables. notre problème est aussi NP-Difficile [45]. Si les contraintes sur la taille des cycles ne sont plus imposées (p = 2), le problème devient alors facile. En effet, on sait que l’ensemble des sous-ensembles d’arêtes qui induisent un graphe dont les composantes contiennent au plus un cycle est un matroïde. Ce matroïde est connu sous le nom du matroïde bi-circulaire (voir [94]). Un simple algorithme glouton peut donc être appliqué pour calculer un réseau de coût total minimum dont les composantes connexes sont unicycliques (voir Chapitre 1).Il est important de signaler qu’il est aussi facile de construire un réseau (graphe) unicyclique (graphe connexe qui contient exactement un seul cycle). Ceci provient du fait que l’ensemble des sous-ensembles d’arêtes qui induisent un graphe qui contient au plus un cycle est aussi un matroïde. Ce matroïde est inclus dans le matroïde bi-circulaire (voir Chapitre 1).

Si les contraintes d’unicyclicité (au plus un cycle) vont être remplacées par des contraintes dites de cyclicité (chaque composante est exactement un cycle) on obtient alors le problème du 2-Couplage (2-factor) qui est un problème facile (voir [117]). Si des contraintes sur la taille des cycles sont ajoutées (pas de cycles de taille inférieure à 5), le problème devient alors difficile (voir [22]).Notre problème a aussi des liens avec le problème de l’étoile-anneau qui consiste à const- ruire un réseau qui contient un seul cycle autour de quelques noeuds, alors que les autres noeuds sont directement liés à ceux qui forment le cycle. Ce problème et quelques variations sont étu- diés dans [2, 82]. Si les contraintes d’unicyclicité sont relaxées, on obtient alors un autre problème connu consistant à trouver un graphe de poids minimum (ou maximum) qui ne contient pas de cycle de taille inférieure à p + 1. Ce problème est équivalent au problème de couverture dans lequel on cherche un ensemble d’arêtes de poids minimum (maximum) intersectant tout cycle dont la taille ne dépasse pas p. Quand p = 3, on sait déjà que le problème est facile si le graphe n’est pas contractible à K.

Ce chapitre est organisé comme suit : les notations et une formulation mathématique sont introduites dans la section suivante. Quelques inégalités valides sont décrites dans la section 3.4. Les faces induites par ces inégalités valides sont étudiées dans la section 2.4. Dans la section 2.5, on présente un algorithme à plans coupants pour résoudre le problème du réseau à composantes connexes et unicycliques de coût total minimum avec la contrainte sur la taille des cycles. Les problèmes de séparation relatifs aux inégalités valides sont étudiés. La section 2.6 est dédiée aux résultats numériques. On cloture ce chapitre par une conclusion qu’on peut trouver en section 2.7. Pour commencer, on sait que le matroïde bi-circulaire est un matroïde transversal [94]. Autrement dit, les ensembles indépendants du matroïde bi-circulaire peuvent être représentés par un couplage. Pour être plus précis, on pose H le graphe biparti dont l’ensemble des sommets est donné par V ∪ E, et il existe une arête entre v ∈ V et e ∈ E si et seulement si v est une extrémité de e. Pour tout couplage de H, l’ensemble des arêtes de E incluses dans ce couplage est un indépendant du matroïde bi-circulaire. Les bases de ce matroïde sont données par des couplages de taille n (en effet, notre problème n’a pas de solution si le rang du matroïde bi-circulaire associé à G est inférieur à n). Les observations données ci-dessus nous aident alors à construire une formulation mathématique des contraintes d’uni-cyclicité. Pour toute arête e = (i, j) ∈ E, on a une variable x