Le problème de partitionnement de graphe est un problème fondamental en optimisation combinatoire. Le problème revient à décomposer l'ensemble des nœuds d'un graphe en plusieurs sous-ensembles disjoints de nœuds (ou clusters), de sorte que la somme des poids des arêtes dont les extrémités se trouvent dans différents clusters est réduite au minimum. Dans cette thèse, nous étudions le problème de partitionnement de graphes avec des poids (non négatifs) sur les nœuds et un ensemble de contraintes supplémentaires sur les clusters (GPP-SC) précisant que la capacité totale (par exemple, le poids total des nœuds dans un cluster, la capacité totale sur les arêtes ayant au moins une extrémité dans un cluster) de chaque groupe ne doit pas dépasser une limite prédéfinie (appelée limite de capacité). Ceci diffère des variantes du problème de partitionnement de graphe le plus souvent abordées dans la littérature en ce que:_ Le nombre de clusters n'est pas imposé (et fait partie de la solution),_ Les poids des nœuds ne sont pas homogènes.Le sujet de ce travail est motivé par le problème de la répartition des tâches dans les structures multicœurs. Le but est de trouver un placement admissible de toutes les tâches sur les processeurs tout en respectant leur capacité de calcul et de minimiser le volume total de la communication inter-processeur. Ce problème peut être formulé comme un problème de partitionnement de graphe sous contraintes de type sac-à-dos (GPKC) sur des graphes peu denses, un cas particulier de GPP-SC. En outre, dans de telles applications, le cas des incertitudes sur les poids des nœuds (poids qui correspondent par exemple à la durée des tâches) doit être pris en compte.La première contribution de ce travail est de prendre en compte le caractère peu dense des graphes G = (V,E) typiques rencontrés dans nos applications. La plupart des modèles de programmation mathématique existants pour le partitionnement de graphe utilisent O(|V|^3) contraintes métriques pour modéliser les partitions de nœuds et donc supposent implicitement que G est un graphe complet. L'utilisation de ces contraintes métriques dans le cas où G n'est pas complet nécessite l'ajout de contraintes qui peuvent augmenter considérablement la taille du programme. Notre résultat montre que, pour le cas où G est un graphe peu dense, nous pouvons réduire le nombre de contraintes métriques à O(|V||E|) [1], [4]... / The graph partitioning problem is a fundamental problem in combinatorial optimization. The problem refers to partitioning the set of nodes of an edge weighted graph in several disjoint node subsets (or clusters), so that the sum of the weights of the edges whose end-nodes are in different clusters is minimized. In this thesis, we study the graph partitioning problem on graph with (non negative) node weights with additional set constraints on the clusters (GPP-SC) specifying that the total capacity (e.g. the total node weight, the total capacity over the edges having at least one end-node in the cluster) of each cluster should not exceed a specified limit (called capacity limit). This differs from the variants of graph partitioning problem most commonly addressed in the literature in that:-The number of clusters is not imposed (and is part of the solution),-The weights of the nodes are not homogeneous.The subject of the present work is motivated by the task allocation problem in multicore structures. The goal is to find a feasible placement of all tasks to processors while respecting their computing capacity and minimizing the total volume of interprocessor communication. This problem can be formulated as a graph partitioning problem under knapsack constraints (GPKC) on sparse graphs, a special case of GPP-SC. Moreover, in such applications, the case of uncertain node weights (weights correspond for example to task durations) has to be taken into account.The first contribution of the present work is to take into account the sparsity character of the graph G = (V,E). Most existing mathematical programming models for the graph partitioning problem use O(|V|^3) metric constraints to model the partition of nodes and thus implicitly assume that G is a complete graph. Using these metric constraints in the case where G is not complete requires adding edges and constraints which may greatly increase the size of the program. Our result shows that for the case where G is a sparse graph, we can reduce the number of metric constraints to O(|V||E|).The second contribution of present work is to compute lower bounds for large size graphs. We propose a new programming model for the graph partitioning problem that make use of only O(m) variables. The model contains cycle inequalities and all inequalities related to the paths in the graph to formulate the feasible partitions. Since there are an exponential number of constraints, solving the model needs a separation method to speed up the computation times. We propose such a separation method that use an all pair shortest path algorithm thus is polynomial time. Computational results show that our new model and method can give tight lower bounds for large size graphs of thousands of nodes.....
| Identifer | oai:union.ndltd.org:theses.fr/2016PA066697 |
| Date | 06 December 2016 |
| Creators | Nguyen, Dang Phuong |
| Contributors | Paris 6, Minoux, Michel, Sirdey, Renaud, Nguyen, Viet Hung |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0022 seconds