Academic literature on the topic 'Optimisation dans des graphes'

L'objet de cette thèse est l'optimisation combinatoire probabiliste de problèmes définis en termes de graphes. Dans ce cadre, un système de probabilités est associé aux sommets du graphe afin de traduire le fait que nous ne connaissons pas le sous-graphe pour lequel le problème sera à résoudre. L'approche utilisée consiste alors à définir une solution dite a priori, qui sous-entend que tous les éléments du graphe d'origine soient présents. Pour une sous-instance donnée, pour laquelle certains éléments du graphe sont absents, il faudra adapter la solution a priori, à l'aide d'un algorithme appelé stratégie de modification, afin qu'elle devienne solution de l'instance considérée. Après avoir situé ces problèmes, par rapport à ceux étudiés dans le cadre de la théorie des graphes aléatoires, nous présentons la méthodologie employée et la formalisons. Nous proposons alors, un état de l'art des travaux réalisés avec cette approche pour les problèmes dont l'instance est un graphe. Puis, nous présentons les résultats que nous avons établis pour les problèmes du stable probabiliste, de la couverture de sommets probabiliste et de plus longs chemins probabilistes. Ceci nous amène a opérer une première classification et structuration de problèmes d'optimisation combinatoire probabilistes selon leur complexité et résolution. La dernière partie de cette thèse, constitue un développement du formalisme du cadre d'étude. Pour cela, nous présentons nos premières réflexions concernant l'utilisation de nouveaux critères. Enfin, nous finissons en introduisant les premières notions nécessaires à la mise en place d'un cadre structure pour l'étude de l'approximation des problèmes d'optimisation combinatoire probabilistes.

La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux<br>The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms

L'objectif de ce travail consiste à réaliser un système dynamique d'aide aux déplacements multimodal pour les voyageurs équipés d'un système d'information tout en prenant en considération les usagers non équipés de ce type de système. Le travail est alors divisé en deux parties: Une partie conception et développement et une partie étude. La partie développement consiste à construire l'outil informatique d'aide aux déplacements grâce à une modélisation multi-agent et qui renvoie à l'usager un itinéraire qui satisfait ces besoins et ceux du réseau. La partie étude quant à elle, consiste en une approche plus théorique qui consiste à déterminer l'impact de l'information sur les coûts des itinéraires, l'impact de la réorientation des usagers vers les transports en commun sur le réseau routier ainsi que l'intérêt de passer vers des véhicules autonomes<br>The objective of this work consists on the realization of a dynamic guidance system in a multimodal network for users equipped with an information device while taking into account users that are not equipped with such devices. The work is organized into parts: a conception part and a theoretical study part. The conception part consists on the development of the guidance tool using a multi agent architecture. This tool assists users in their daily travels by giving them the itinerary that suits best not only their needs but also the overall network. The theoretical study emphasizes on how the performance of the network can be enhanced. To do so, three main studies will be presented: the impact of the information on the cost of the itineraries, the impact of the reorientation of users towards transportation systems on the road network and finally the benefits of introducing autonomous vehicles

Sont presentes des differents travaux ayant trait au probleme de l'independant de poids maximum. Il est decrit un algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans k::(1,3). Les graphes parfaits sont etudies. Un theoreme reduisant la h-perfection d'un graphe g a la h-perfection d'un sous-graphe propre de g est demontre. Il est presente une operation de reduction preservant la h-perfection. Un algorithme polynomial de reconnaissance des graphes sans k::(1,3) parfaits est propose. Presentation de cinq theoremes de decomposition des graphes parfaits en termes de p::(4)-structure

Cette thèse propose un cadre d'évaluation pour des requêtes XQuery dans un contexte de médiation de données XML. Un médiateur doit fédérer des sources de données distribuées et hétérogènes. A cette fin, un modèle de représentation des requêtes est nécessaire. Ce modèle doit intégrer les problèmes de médiation et permettre de définir un cadre d'optimisation pour améliorer les performances. Le modèle des motifs d'arbres est souvent utilisé pour représenter les requêtes Xquery, mais il ne reconnait pas toutes les spécifications du langage. La complexité du langage XQuery fait qu'aucun modèle de représentation complet n'a été proposé pour reconnaitre toutes les spécifications. Ainsi, nous proposons un nouveau modèle de représentation pour toutes les requêtes XQuery non typées que nous appelons TGV. Avant de modéliser une requête, un étape de canonisation permet de produire une forma canonique pour ces requêtes, facilitant l'étape de traduction vers le modèle TGV. Ce modèle prend en compte le contexte de médiation et facilite l'étape d'optimisation. Les TGV définis sous forme de types abstraits de données facilitent l'intégration du modèle dans tout sytème en fonction du modèle de données. De plus, une algèbre d'évaluation est définie pour les TGV. Grâce à l'intégration d'annotations et d'un cadre pour règles de transformation, un optimisateur extensible manipule les TGV. Celui-ci repose sur des règles de transformations, un modèle de coût générique et une stratégie de recherche. Les TGV et l'optimisateur extensible sont intégrés dans le médiateur XLive, développé au laboratoire PRISM<br>This thesis proposes to evaluate XQuery queries into a mediation context. This mediator must federate several heterogeneous data sources with an appropriate query model. On this model, an optimization framework must be defined to increase performance. The well-known tree pattern model can represent a subset of XPath queries in a tree form. Because of the complexity of XQuery, no model has been proposed that is able to represent all the structural components of the language. Then, we propose a new logical model for XQuery queries called TGV. It aims at supporting the whole XQuery into a canonical form in order to check more XQuery specifications. This form allows us to translate in a unique way queries into our TGV model. This model takes into account a distributed heterogenous context and eases the optimization process. It integrates transformation rules, cost evaluation, and therefore, execution of XQuery queries. The TGV can be used as a basis for processing XQuery queries, since it is flexible, it provides abstracts data types wich can be implemented according to the underneath data model. Moreover, it allows user-defined annotating ans also cost-related annotating for cost estimation. Althouogh the model will be useful, it relies on XQuery complicates specifications. TGV are illustrated in this thesis with several figures on W3C's uses cases. Finally, a framework to define transformation rules is added to the extensible optimizer to increase the XLive mediator performances. The XLive mediation system has been developped at the PRISM laboratory

Pour permettre une plus grande capacité de calcul les concepteurs de systèmes embarqués se tournent aujourd'hui vers les MPSoC. Malheureusement, ces systèmes sont difficiles à programmer. Un des problèmes durs est l'expression et l'optimisation des réorganisations de données au sein d'un programme. Dans cette thèse nous souhaitons proposer une chaîne de compilation qui : 1) propose une syntaxe simple et haut-niveau pour exprimer le découpage et la réorganisation des données d'un programme parallèle ; 2) définisse une exécution déterministe du programme (critique dans le cadre des systèmes embarqués) ; 3) optimise et adapte les programmes aux contraintes de l'architecture. Pour répondre au point 1) nous proposons un langage haut-niveau, SLICES, qui permet de décrire les réorganisation de données à travers des découpages multidimensionnels. Pour répondre au point 2) nous montrons qu'il est possible de compiler SLICES vers un langage de flots de données, SJD, qui s'inscrit dans le modèle des Cyclostatic Data-Flow et donc admet une exécution déterministe. Pour répondre au point 3) nous définissons un ensemble de transformations qui préservent la sémantique des programmes SJD. Nous montrons qu'il existe un sous-ensemble de ces transformations qui génère un espace de programmes équivalents fini. Nous proposons une heuristique pour explorer cet espace de manière à choisir la variante la plus adaptée à notre architecture. Enfin nous évaluons cette méthode sur deux problèmes classiques : la réduction de la mémoire consommée et la réduction des communications d'une application parallèle.

Cette synthèse de travaux de recherche concerne l'algorithmique dans les graphes et l'utilisation de la pro- grammation linéaire et semidéfinie positive (SDP) dans le cadre de la résolution exacte ou approchée de plusieurs problèmes fondamentaux de l'Optimisation Combinatoire. L'approche semidéfinie, qui conduit à des relaxations convexes mais non-linéaires, a permis d'obtenir de remarquables résultats théoriques en approximation et devient à présent utilisable en pratique (tout comme la programmation linéaire qui en est un cas particulier). Nos travaux comportent une forte composante algorithmique et des études de complexité de plusieurs problèmes d'optimisation dans les graphes. Nous considérons tout d'abord le problème de la recherche d'un sous-graphe dense de taille fixée pour lequel nous présentons un algorithme polynomial avec ga- ranties de performances fondé sur la programmation linéaire et quadratique. Puis, nous étudions les problèmes de multiflots entiers et de multicoupes pour lesquels nous avons identifié de nombreux cas po- lynomiaux dans des graphes particuliers importants en pratique : arborescences, grilles, anneaux. D'une part, les solutions fractionnaires fournies par certaines relaxations linéaires de ces problèmes sont le point de départ d'algorithmes de résolution efficaces. D'autre part, les propriétés des programmes linéaires uti- lisés nous permettent également d'élaborer des algorithmes purement combinatoires et de démontrer leur validité (matrices totalement unimodulaires, théorème des écarts complémentaires). Nous proposons également des approches systématiques pour élaborer des relaxations semidéfinies pour les programmes quadratiques, modèles de très nombreux problèmes combinatoires et continus. Plus précisément, nous étudions les liens entre relaxations semidéfinies et des relaxations lagrangiennes partielles de programmes quadratiques contenant des contraintes linéaires. En particulier, les fonctions quadratiques constantes sur une variété affine sont entièrement caractérisées. Ceci permet de facilement comparer les différentes familles de contraintes redondantes proposées dans la littérature dans l'approche semidéfinie dans le cadre unifié de l'approche lagrangienne. Puis, nous présentons un algorithme pour élaborer des relaxations semidéfinies à partir de relaxations linéaires existantes. L'objectif est de pro- fiter des résultats théoriques et expérimentaux obtenus dans l'approche linéaire. Nous avons développé un logiciel (SDP_S) grâce à ces résultats. Il permet de formuler automatiquement et facilement des relaxations semidéfinies pour tout problème pouvant être formulé comme un programme quadratique en variables bivalentes. Notre méthode peut se généraliser à certains programmes à variables mixtes. Enfin, nous appliquons les méthodes décrites précédemment à une série de problèmes combinatoires classiques. Nos expérimentations montrent que l'approche semidéfinie est à présent pertinente dans la pra- tique sous certaines conditions. Premièrement, nous présentons des méthodes de séparation/évaluation efficaces fondées sur la SDP pour la résolution exacte des problèmes max 2sat et Vertex-Cover. Deuxièmement, nous proposons plusieurs bornes par SDP de grande qualité pour des problèmes particu- lièrement difficiles à résoudre par les approches linéaires : k-cluster, CMAP (un problème de placement de tâches avec contraintes de ressources), et le problème de l'affectation quadratique (QAP). Pour ce dernier nous présentons également un algorithme de coupes performant fondé sur la programmation semidéfinie. Afin d'obtenir des algorithmes efficaces en pratique, nous mettons en oeuvre non seulement nos méthodes d'élaboration de relaxations SDP, mais également des techniques algorithmiques issues de l'approximation polynomiale, ainsi que des outils spécifiques de résolution numérique des programmes semidéfinis.

Cette thèse concerne l’étude de l’algorithmique et de la complexité des communications radio. En particulier, nous nous sommes intéressés au problème de rassembler les informations des sommets d’un réseau radio en nœud central. Ce problème est motivé par une question de France Telecom (Orange Labs) : « comment amener Internet dans les villages ». Les sommets représentent les maisons des villages qui communiquent entre elles par radio, le but étant d’atteindre une passerelle connectée à Internet par une liaison satellite. Le même problème se rencontre dans les réseaux de senseurs où il s’agit de collecter les informations des senseurs dans une station de base. Une particularité des réseaux radio est que la distance de transmission est limitée et que les transmissions interfèrent entre elles (phénomènes d’interférences). Nous modélisons ces contraintes en disant que deux sommets (équipements radio) peuvent communiquer s’ils sont à distance au plus dT et qu’un nœud interfère avec un autre si leur distance est au plus dI. Les distances sont considérées dans un graphe représentant le réseau. Une étape de communication consistera donc en un ensemble de transmissions compatibles (n’interférant pas). Notre objectif est de trouver le nombre minimum d’étapes nécessaires pour réaliser un tel rassemblement et de concevoir des algorithmes réalisant ce minimum. Pour des topologies particulières comme le chemin et la grille, nous avons établi des résultats optimaux ou quasi optimaux. Nous avons aussi considéré le cas systolique (ou continu) où on veut maximiser le débit offert à chaque nœud<br>This thesis concerns the study of the algorithmic and the complexity of the communication in radio networks. In particular, we were interested in the problem of gathering information from the nodes of a radio network in a central node. This problem is motivated by a question of France Telecom (Orange Labs) “How to bring Internet in villages”. Nodes represent the houses of the villages which communicate between them by radio, the goal being to reach a gateway connected to Internet by a satellite link. The same problem can be found in sensor networks where the question is to collect data from sensors to a base station. A peculiarity of radio networks is that the transmission distance is limited and that the transmissions interfere between them (interference phenomena). We model these constraints by saying that two nodes (radio devices) can communicate if they are at distance at most dT and a node interferes with another one if their distance is at most dI. The distances are considered in a graph representing the network. Thus, a communication step will consist in a compatible (non interfering) set of transmissions. Our goal is to find the minimum number of steps needed to achieve such a gathering and design algorithms achieving this minimum. For special topologies such as the path and the grid, we have proposed optimal or near optimal solutions. We also considered the systolic (or continuous) case where we want to maximize the throughput (bandwidth) offered to each node

Dans de nombreuses applications telles que la médecine, l'environnement ou les biotechnologies par exemple, la découverte de nouveau processus de régulations de gènes permet une meilleure compréhension des réponses phénotypiques des cellules à des stimuli externes. Pour cela, il est alors d'usage de générer et d'analyser les données transcriptomiques issues d'expériences de types puces à ADN ou plus récemment de RNAseq. Ainsi, pour chaque gène d'un organisme d'étude placé dans différentes conditions expérimentales, un ensemble de niveau d'expression est obtenu. A partir de ces données, les mécanismes de régulation des gènes peuvent être obtenus à travers un ensemble de liens dans des graphes. Dans ces réseaux, les nœuds correspondent aux gènes. A lien entre deux nœuds est identifié si une relation de régulation existent entre les deux gènes correspondant. De tels réseaux sont appelés Réseaux de Régulation de Gènes (RRGs). Malgré la profusion de méthodes d'inférence disponible, leur construction et leur analyse restent encore à ce jour un défi.Dans cette thèse, nous proposons de répondre au problème d'inférence de réseaux par des techniques d'optimisation dans des graphes. A partir d'information de régulation sur l'ensemble des couples de gènes, nous proposons de déterminer la présence d'arêtes dans le RRG final en adoptant une formulation de fonction objectif intégrant des contraintes. Des a priori à la fois biologiques (sur les interactions entre les gènes) et structuraux (sur la connectivité des nœuds) ont été considérés pour restreindre l'espace des solutions possibles. Les différents a priori donnent des fonctions objectifs ayant des propriétés différentes, pour lesquelles des stratégies d'optimisation adaptées (continue et/ou discrète) peuvent être appliquées. Les post-traitement que nous avons développé ont mené à un ensemble de méthodes nommés BRANE, pour "Biologically-Related A priori for Network Enhancement". Pour chacune des méthodes développées (BRANE Cut, BRANE Relax et BRANE Clust), nos contributions sont triples : formulation de la fonction objectif à l'aide d'a priori, développement de la stratégie d'optimisation et validation (numérique et biologique) sur des données de parangonnage issues des challenges DREAM4 et DREAM5, montrant ainsi des améliorations pouvant atteindre 20%.En complément de l'inférence de réseaux, notre travail s'est étendu à des traitements de données sur graphe plus génériques, tels que les problèmes inverses. Nous avons notamment étudié HOGMep, une approche Bayésienne utilisant des stratégies d'approximation Bayésienne variationnelle. Cette méthode a été développée pour résoudre de façon conjointe, des problèmes de restauration et de classification sur des données multi-composantes (signaux et images). Les performances d'HOGMep dans un contexte de déconvolution d'image couleur montrent de bonnes qualités de reconstruction et de segmentation. Une étude préliminaire dans un contexte de classification de données médicales liant génotype et phénotype a également montré des résultats prometteurs pour des adaptions à venir en bioinformatiques<br>The discovery of novel gene regulatory processes improves the understanding of cell phenotypicresponses to external stimuli for many biological applications, such as medicine, environmentor biotechnologies. To this purpose, transcriptomic data are generated and analyzed from mi-croarrays or more recently RNAseq experiments. For each gene of a studied organism placed indifferent living conditions, they consist in a sequence of genetic expression levels. From thesedata, gene regulation mechanisms can be recovered by revealing topological links encoded ingeometric graphs. In regulatory graphs, nodes correspond to genes. A link between two nodesis identified if a regulation relationship exists between the two corresponding genes. Such net-works are called Gene Regulatory Networks (GRNs). Their construction as well as their analysisremain challenging despite the large number of available inference methods.In this thesis, we propose to address this network inference problem with recently developedtechniques pertaining to graph optimization. Given all the pairwise gene regulation informa-tion available, we propose to determine the presence of edges in the final GRN by adoptingan energy optimization formulation integrating additional constraints. Either biological (infor-mation about gene interactions) or structural (information about node connectivity) a priorihave been considered to reduce the space of possible solutions. Different priors lead to differentproperties of the global cost function, for which various optimization strategies can be applied.The post-processing network refinements we proposed led to a software suite named BRANE for“Biologically-Related A priori for Network Enhancement”. For each of the proposed methodsBRANE Cut, BRANE Relax and BRANE Clust, our contributions are threefold: a priori-based for-mulation, design of the optimization strategy and validation (numerical and/or biological) onbenchmark datasets.In a ramification of this thesis, we slide from graph inference to more generic data processingsuch as inverse problems. We notably invest in HOGMep, a Bayesian-based approach using aVariation Bayesian Approximation framework for its resolution. This approach allows to jointlyperform reconstruction and clustering/segmentation tasks on multi-component data (for instancesignals or images). Its performance in a color image deconvolution context demonstrates bothquality of reconstruction and segmentation. A preliminary study in a medical data classificationcontext linking genotype and phenotype yields promising results for forthcoming bioinformaticsadaptations