A hybrid algorithm for the Partition Coloring Problem

Abstract

Das Partition Coloring Problem (PCP) generalisiert das Vertex Coloring Problem (VCP) durch Unterteilung der Knotenmenge in Gruppen und besteht aus der Berechnung einer Knotenfärbung des durch Selektion genau eines Knotens pro Gruppe induzierten Subgraphens. Das PCP gehört zur Gruppe der so genannten NP -schweren Probleme, i.e. Probleme für die kein effizien- tes Verfahren zur Berechnung einer exakten Lösung besteht. Eine seiner Anwendungen besteht in der Zuordnung von Wellenlängen zu Datenübertragungsleitungen optischer Computernetzwerke, wie sie heute beispielsweise als Backbone in der Infrastruktur des Internets vorkommen. Im Gegensatz zum VCP bleibt das PCP bis heute wenig erforscht. Diese Arbeit präsentiert ein metaheuristisches Verfahren Hybrid-PCP zur Lösung des PCP, dass sich zusätzlich exakter Methoden bedient um Teilprobleme zu lösen. Dabei wird eine Verbesserungsstrategie verfolgt, in der Knoten in spezifischen Teilgraphen neu selektiert und eingefärbt werden, wobei temporär auch ungültige Lösungen zugelassen werden. Die Gültigkeit wird danach mittels Tabusuche wiederhergestellt. Die Hauptinnovation dieser Arbeit liegt im Aufwand, der für die Neuselektion und -einfärbung der Teilgraphen aufgewendet wird, als dass dafür eine Heuristik und zwei mathematische Programmformulierungen eingesetzt werden. Der Algorithmus wird mit unterschiedlicher Parametrisierung als auch leichten Variationen evaluiert, die Ergebnisse miteinander und mit solcher vorhergehender Arbeiten verglichen. Weitere Experimente werden mit der Erstellung initialer Lösungen durchgeführt, wobei zwei bereits bekannte Algorithmen OneStepCD und eine Adaption des für VCP entwickelten DANGER Algorithmus miteinander verglichen werden. Hybrid-PCP kann betreffend Lösungsqualität und Laufzeit mit den besten bisher gefundener Lösungsansätze konkurrieren. Der Autor legt weiters eine Reflexion des Verfahrens sowie einen Verbesserungsvorschlag dar.

The Partition Coloring Problem (PCP) generalizes the classical Vertex Coloring Problem (VCP) by partitioning the set of nodes into clusters and aims to find a coloring for the subgraph induced by selecting exactly one node of each cluster. It is a member of the class of so called NP-hard problems, i.e. problems without a known algorithm for solving it efficiently. One of the real world applications for PCP is the assignment of wavelengths to data transmitting connections of all optical computer networks, as they appear as backbones of the Internet infrastructure of our time. In opposition to VCP, not much research has been investigated in PCP so far. This thesis presents an approach Hybrid-PCP tackling the PCP by means of metaheuristics combined with exact approaches for solving subproblems. Therefore an improvement strategy is applied, where nodes in specific subgraphs are reselected and recolored, temporarily allowing infeasible solutions. Feasibility is then reacquired by using a tabu search. The main innovation of the approach is the effort that is put in the process of node reselection and reassignment, where a heuristic and two Integer Linear Program (ILP) formulations are used. The algorithm is evaluated using different parameter settings as well as slight variations, the results are compared to each other as well as to previous works. Further experiments have been made on gaining initial solutions, comparing two already known algorithms OneStepCD and an adaptation of DANGER. Hybrid-PCP can compete with the best heuristics known so far in terms of solution quality and runtime. A reflection of the approach as well as a proposal for improvement is explained.