a composantes unicycliques avec de nouvelles contraintes techniques

a composantes unicycliques avec de nouvelles contraintes techniques

L’objet de ce chapitre est d’intégrer d’autres types de contraintes. Nous souhaitons toujours obtenir un réseau à composantes connexes unicycliques. Nous considérons dans un premier temps des contraintes de degré. Ensuite, on intègre une contrainte sur le nombre de compo- santes connexes. Enfin, nous décrivons comment on peut intégrer des contraintes d’apparte- nance de sommets à une même composante connexe ainsi que des contraintes de séparation de certains sommets. Quelques résultats expérimentaux seront également présentés. Signalons que l’étude faite dans ce chapitre est très préliminaire. Les travaux exposés dans les deux précédents chapitres ont permis d’intégrer des contraintes techniques importantes en plus de la contrainte d’unicyclicité : taille minimale des cycles, et contraintes de type Steiner. Nous continuons sur la même lancée en intégrant d’autres contraintes. Signalons cependant que l’étude faite dans ce chapitre reste superficielle puisque nous n’avons pas pu faire une étude polyèdrale poussée. Nous espérons pouvoir approfondir ce travail ulté- rieurement.Notons qu’en ce qui concerne les résultats expérimentaux qui vont suivre pour chaque cas, nous avons implémenté un algorithme à plans coupants suivi d’un algorithme de Branch&Cut basé sur les fonctions callbacks de [74]. Toutes les expérimentations ont été réalisées sur un Pentium 4, de 3.25 Go de RAM, et de 2.39 GHz de fréquence. On note aussi qu’une stratégie de recherche en profondeur d’abord a été choisie dans l’algorithme de Branch&Cut. Dans certains cas, une borne supérieure est calculée lorsque c’est possible.Notons également que lorsque la solution est entière, les inégalités (4.3) sont suffisantes pour garantir que le nombre de composantes connexes est au plus z. Cependant, les inégalités sont insuffisantes pour décrire l’enveloppe convexes des réseaux respectant la contrainte.On a limité le temps total d’exécution à 7200 secondes. Le nombre maximum de compo- santes unicycliques à obtenir varie de 1 à 3 (sauf pour n = 20, cette instance donne un parti- tionnement initial limité à 2 composantes unicycliques au plus). Si ce nombre est de 1, alors on utilise la résolution de l’algorithme glouton donné dans le chapitre 1, ce qui explique les temps de calcul nuls dans ce cas. Les instances traitées relèvent de graphes aléatoires et Euclidiens générés 3 fois. Les résultats présentés sont des moyennes sur les 3 instances.

Pour tester l’efficacité de ces inégalités, on a réalisé quelques expérimentations numériques. Pour plusieurs valeurs de n (nombre de noeuds), on génére des instances Euclidiennes aléatoires où on cherche à séparer certains couples de sommets. Pour chaque valeur de n et chaque valeur du nombre de couples à séparer, nous générons 3 instances. Les résultats présentés sont donc les moyennes des résultats des 3 instances.Les résultats présentés dans le tableau 4.2 semblent montrer que les inégalités (4.4) per- mettent de résoudre des instances de grandes tailles. Notons cependant que le nombre de noeuds dans l’arbre de recherche peut devenir assez élevé. La difficulté du problème semble augmenter avec le nombre de couples à séparer.Il est facile de prouver que le problème de synthèse d’un réseau à composantes connexes unicycliques respectant des contraintes d’appartenance de certains sommets à une même com- posante connexe est un problème NP-dur. Une réduction à partir de l’arbre de Steiner est quasi- immédiate. Quelques résultats numériques sont résumés dans le tableau 4.3. Les expériences ont été conduites d’une manière similaire à ce qui a été fait précédemment : instances Euclidiennes, plusieurs valeurs pour le nombre de couples à séparer, 3 instances pour chaque variante, un algorithme à plans coupants suivi d’un Branch&Cut.

On peut également essayer d’intégrer plusieurs combinaisons des contraintes décrites dans ce chapitre. Ceci est déjà possible dans le logiciel réalisé dans cette thèse. Cependant, plus de travail est nécessaire pour réduire les temps de calcul. Après avoir étudié plusieurs variantes du problème de synthèse de réseaux à composantes connexes unicycliques, nous allons considérer deux classes particulières de graphes unicy- cliques. Nous étudions le spectre des matrices d’adjacence et des Laplaciens associés à ces graphes. Outre l’intérêt théorique de ces résultats, la connaissance des valeurs propres extré- males pourrait renforcer les relaxations linéaires utilisées dans la synthèse de ce type de ré- seaux. L’étude du spectre des matrices associées à un graphe permet d’avoir des éclairages intéres- sants sur la structure du graphe. Elle peut même être à l’origine d’algorithmes combinatoires. Rappelons par exemple que la programmation semi-définie positive est équivalente à optimiser dans l’ensemble des matrices dont toutes les valeurs propres sont positives.