The Minimum Labeling Spanning Tree and Related Problems
Institution:
AvignonDisciplines:
Directors:
Abstract EN:
The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph inwhich each edge has one label associated, by using a minimum number of labels. It is anNP-hard problem that has attracted substantial research attention in recent years. In its turn,the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of theMLSTP that allows the situation in which multiple labels can be assigned to an edge. Bothproblems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. This thesis addressesseveral connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in this work can beclassified between theoretical and practical. On the theoretical side, we have introduced newuseful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well asa polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics— such as the metaheuristic-based algorithm MSLB, and the constructive heuristic pMVCA —and exact methods — such as new mathematical formulations and branch-and-cut algorithms —for solving the GMLSTP. Computational experiments over well established benchmarks for theMLSTP are reported, showing that the new approaches introduced in this work have achievedthe best results for both heuristic and exact methods in comparison with the state-of-the-artmethods in the literature.
Abstract FR:
Soit L un ensemble fini d’éléments appelés étiquettes. On appelle graphe étiqueté simple, un graphe simple dans lequel à chaque arête est associée une étiquette prise dans L. Le problème de l’arbre couvrant de nombre d’étiquettes minimal (en anglais: the minimum labeling spanning tree problem, MLSTP) est un problème d’optimisation combinatoire consistant à trouver un arbre couvrant dans un graphe étiqueté simple en utilisant un nombre minimum d’étiquettes. Le problème est NP-dur. Il a fait l’objet d’un nombre important de recherche au cours des dernières années. L’une de ces directions de recherche a par ailleurs conduit à l’étude d’une généralisation du problème dite problème généralisée de l’arbre couvrant de nombre d’étiquettes minimal(en anglais: the generalized minimum labeling spanning tree problem, GMLSTP). Le problème GMLSTP modélise les situations dans lesquelles plusieurs étiquettes peuvent être assignées à un arête. Les deux problèmes ont plusieurs applications pratiques dans des domaines importants tels que la conception de réseaux informatiques, la conception de réseaux de transport multimodaux et la compression de données. Nous proposons dans cette thèse plusieurs résultats théoriques contribuant à l’implantation de nouveaux schémas de résolution pratique de ces problèmes. En particulier, sur le plan théorique, nous avons introduit de nouveaux concepts, définitions, propriétés et théorèmes utiles, ainsi qu’une étude polyédrale du domaine des points réalisables d’une nouvelle formulation de GMLSTP. Cette formulation et son analyse ont permi le développement d’algorithmes de branchement et de coupe (branch-and-cut) pour la résolution exacte des problèmes. De nouvelles heuristiques ont été également développées — telles que l’algorithme basé sur la métaheuristique MSLB, et l’heuristique constructive pMVCA. Des résultats d’expériences numériques sur des benchmarks du problème MLSTP sont données. Elles démontrent la qualité des approches proposées dans cette thèse puisque, aussi bien pour les approches exactes qu’approchées, nous obtenons, comparativement à l’état de l’art du domaine, les meilleurs résultats de la littérature.