Search

In this thesis, we use the polyhedral approach to solve combinatorial problems in telecommunications context. First, we introduce the problem of network design with unicyclic connected components. We recall that without other constraints, our problem is easy to solve, and we propose a study with new technical constraints. We start our study by adding constraints on the size of cycles. We aim to obtain unicyclic components such that the size of each cycle is not lower than a certain p. This problem is NP-Hard. We describe some valid inequalities for the design of unicyclic graphs with girth constraints. The faces induced by these valid inequalities are also studied. Some of them can be separated in polynomial time. A cutting plane algorithm based on these inequalities is implemented to solve the problem. Furthermore, we focus on a Steiner type problem, which consists in partitioning the graph to unicyclic components, such that some given vertices belong to a cycle. We prove then that our problem is easy to solve, and we propose an exact extended formulation and a partial description of the convex hull of the incidence vectors of our Steiner network problem. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg&Rao algorithm to separate blossom inequalities. Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, we study the spectra of two specified classes of unicyclic graphs., Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. Mots clés : Optimisation Combinatoire, Polyèdres, Algorithme à Plans Coupants, Graphes

International audience; This article focuses on the problem of computing a minimum-weight subgraph with unicyclic connected components. Although this problem is generally easy, it becomes difficult when a girth constraint is added. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Hence, the problem is solved by a cutting-plane algorithm based on these inequalities and using a compact formulation derived from the transversality of the bicircular matroid. Numerical results are also presented.

National audience; La théorie des jeux est largement utilisée pour proposer des études sur le comportement des acteurs en compétition pour acquérir un bien ou un service. Il existe d'importants travaux de recherche consacrés à des modèles de jeux dans les réseaux. On cite par exemple des modèles de jeux sur des problèmes de contrôle d'accès, de coopération entre domaines administratifs ou d'opérateurs, de sécurité, et de tarification. Cet article se place dans un nouvel environnement dit "nuage d'information" ou alors Cloud. Ce dernier est constitué de plusieurs fournisseurs de services qui sont en interaction avec un ensemble fini d'utilisateurs souhaitant partager des ressources comme des machines virtuelles, des puissances de calcul, des réseaux, etc. Les fournisseurs de services cherchent à maximiser leurs revenus tout en garantissant un apport positif aux objectifs des utilisateurs. Une variante de ce type de problèmes a été déjà abordée dans [1, 2]. Les auteurs de [1] ont proposé un modèle de jeu à la Stackelberg pour résoudre un problème de tarification s'appuyant sur les demandes des utilisateurs. Dans notre travail, la fonction utilité de chaque utilisateur est modélisée sous forme d'une fonction concave des demandes exprimées en bande passante allouée par chaque fournisseur. Les fournisseurs de services proposent alors des prix unitaires aux utilisateurs qui eux même adaptent leurs demandes en fonction des prix proposés. Les fournisseurs de service du cloud en retour adaptent leurs prix en fonction des demandes des utilisateurs. Le problème consiste alors à déterminer les prix optimums proposés par les fournisseurs et les demandes optimales des utilisateurs sous la contrainte de la bande passante totale à ne pas dépasser

International audience; *

National audience; Étant donné un graphe pondéré G, nous souhaitons dans un premier temps partitionner les sommets de G en plusieurs composantes connexes unicycliques de coût total minimum. Pour cela, on développe deux algorithmes polynômiaux, le premier se base sur la théorie des matroïdes alors que le deuxième est un algorithme de couplage maximum de poids minimum. On généralise ce problème en y ajoutant différentes contraintes (taille des cycles, contraintes d'appartenance d'un certain nombre de sommets aux cycles des composantes connexes, nombre maximum des composantes connexes). Une étude polyèdrale est alors proposée. Plusieurs inégalités valides sont mise en évidence, et les faces induites par ces inégalités sont étudiées

International audience; Let G a weighted connexe graph. In this paper, we are interesting by covering the vertices of G by connexe disjoints unicyclic components with minimum total cost. We propose two polynomial algorithms, the first is based on the construction of a matroïd on this graph, and the second is to calculate in polynomial time a maximum matching with minimum cost on an induced graph constructed on the initial one. We prove that this two methods have the same result which is disjoints connexe unicyclic components with minimum total cost. In a second time, we are interesting by obtain a partition of unicyclic components with a minimum total cost by adding a girth constraint. Then the problem becomes difficult, and to solve it, we propose a polyhedral study in which we show many facets and valid inequalities. Some of them can be exactly separated in polynomial time. Then we solve the problem by a cutting plane algorithm based on these inequalities and using a compact formulation issued from the transversality of the bicircular matroïd. We also show a new valid inequality related to the upper bound of the number of unicyclic components obtained after the partition. The problem has practical and important applications in the design of telecommunication networks

National audience; *