Faculté des sciences de base SB, Section de mathématiques, Institut de mathématiques IMA (Chaire de recherche opérationnelle SE ROSE)

Suboptimal colorings and solution of large chromatic scheduling problems

Blöchliger, Ivo ; Werra, Dominique de (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3363.

Ajouter à la liste personnelle
    Summary
    Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution will be reported), see [Cul] for a list of over 450 references. The graph coloring problem involves coloring the vertices of a given graph in such a way that two adjacent vertices never share the same color. The goal is to find the smallest number of colors needed to color all vertices in a fashion that satisfies this requirement. This number is called chromatic number and is denoted by Χ. In the first chapter, we present our research on suboptimal colorings and graphs which can be colored in such a way that the number of different colors appearing on the closed neighborhood (a vertex plus its neighbors) of any vertex v is less than Χ. We call such graphs oligomatic. The most interesting result is the following: given a graph and a coloring using Χ + p colors, there exists a vertex v such that there are at least Χ different colors among all vertices which are at a distance of [p/2] + 1 or less from v. We also study the existence of oligomatic graphs in special classes. Additionally, we present results of research on universal graphs which are "generic" oligomatic graphs in the sense that most properties of oligomatic graphs can be analyzed by restricting ourselves to universal graphs. Chapters Two to Four deal with the development of heuristics for two types of graph coloring problems. The tabu search heuristic was a central focus of our research. A tabu search iteratively modifies a candidate solution (which becomes the new candidate solution) with the goal of improving it. In such a procedure it is forbidden (tabu) to undo a modification for a certain number iterations. This mechanism allows to escape from local minima. In Chapter Two, we propose general improvements for tabu search based on some new and simple mechanisms (called reactive tabu schemes) to adapt the tabu tenure (which corresponds to the number of iterations a modification stays tabu). We also introduce distance and similarity measures for graph coloring problems which are needed in iterative procedures such as those of the tabu search. In the third chapter, we present the PARTIALCOL heuristic for the graph coloring problem. This method obtains excellent results compared to other similar methods and is able to color the well known DIMACS [JT96] benchmark graph flat300_28_0 optimally with 28 colors. (The best colorings found to date by other researchers use at least 31 colors.) PARTIALCOL uses partial solutions in its search space, which is a little explored way of approaching the graph coloring problem. Most approaches either use colorings and try to minimize the number of colors, or they use improper colorings (having conflicts, i.e. adjacent vertices which may have the same color) and try to minimize the number of conflicts. In the final chapter, we present a weighted version of the graph coloring problem which has applications in batch scheduling and telecommunication problems. We present two different adaptations of tabu search to the weighted graph coloring problem and test several of the reactive tabu schemes presented in Chapter Two. Further, we devise an adaptive memory algorithm AMA inspired by genetic algorithms. A large set of benchmark graphs with different properties is presented. All benchmark graphs with known optima have been solved to optimality by AMA. A key element of this algorithm is its capacity to determine the number k of colors to be used. Most other graph coloring heuristics need this parameter to be supplied by the user. Considering the results obtained on various graphs, we are confident that the methods developed are very efficient.
    Résumé
    La coloration de graphes est un sujet de recherche très actuel, dans la théorie des graphes ainsi que pour la conception d'heuristiques pour la résolution de problèmes qui ne peuvent pas être résolus exactement parce que le temps de calcul nécessaire croît trop vite avec la taille du problème. Le problème de la coloration de graphes (GCP) consiste à colorer les sommets d'un graphe d'une manière que deux sommets adjacents ne reçoivent jamais la même couleur. La question est quel est le nombre minimum de couleurs nécessaires pour colorer un graphe donné ? Ce nombre est appelé nombre chromatique et est noté par Χ (prononcé ki). Au premier chapitre nous présentons les résultats de nos recherches sur les colorations suboptimales et des graphes qui peuvent être colorés de sorte que le nombre de couleurs apparaissant sur chaque sommet et ses voisins soit inférieure à Χ. Nous appelons ces graphes oligomatiques. Le résultat le plus important est le théorème suivant : Pour un graphe coloré avec Χ + p couleurs, il existe un sommet v tel qu'il y a au moins Χ couleurs différentes sur l'ensemble des sommets qui se trouvent à une distance d'au plus [p/2] + 1 de v. Nous avons également étudié l'existence de graphes oligomatiques dans différent classes de graphes. Nous présentons également des résultats sur les graphes universels qui servent comme modèle pour les graphes oligomatiques : il suffit souvent, en effet, d'étudier les graphes universels pour en dériver des propriétés des graphes oligomatiques. Nous développons des améliorations de l'heuristique tabu search appliquée au GCP ainsi qu'à une généralisation pondérée du GCP. Puis nous introduisons plusieurs méthodes, appelées reactive tabu schemes, pour ajuster automatiquement la tabu tenure, le paramètre crucial pour tabu search. Pour ces méthodes, nous introduisons des mesures de distance et de similarité entre deux colorations d'un graphe. Au troisième chapitre nous présentons l'heuristique PARTIALCOL pour le GCP. Cette heuristique obtient des résultats excellents sur des graphes de test DIMACS. En particulier cette méthode est capable de colorer le graphe flat300_28_0 avec le nombre optimal de 28 couleurs, ce qu'aucune autre méthode connue à ce jour n'a pu obtenir (la meilleure coloration trouvé utilisait 31 couleurs). PARTIALCOL utilise des colorations partielles (certains sommets ne sont pas colorés), ce qui est une méthode peu explorée dans le cadre du GCP. Nous présentons deux adaptations de tabu search à une version pondérée du GCP. La première utilise des colorations avec un nombre variable de couleurs, tandis que la deuxième utilise des colorations avec conflits (des sommets adjacents peuvent avoir la même couleur) avec un nombre de couleurs fixé par l'utilisateur. Avec les deux approches, plusieurs reactive tabu schemes ont été testés. Basé sur la première approche, nous avons développé un algorithme à mémoire adaptative (AMA). Pour tester ces heuristiques, nous avons généré un jeux d'instances avec différentes caractéristiques. Toutes les instances avec un optimum connu ont été résolues par AMA. Une propriété importante de cet algorithme est le fait qu'il détermine automatiquement le nombre de couleurs à utiliser, contrairement à beaucoup d'autres heuristiques de coloration qui demandent ce paramètre comme entrée. Les résultats obtenus avec les heuristiques développées confirment leur efficacité et le bienfond é des idées sous-jacentes. Ces techniques vont très certainement permettre d'aborder d'autres problèmes d'optimisation combinatoire et d'améliorer substantiellement les performances atteintes jusqu'ici.