Clustering Heuristics for the Hierarchical Ring Network Problem

Authors: 
Rainer Schuster
Type: 
Master thesis
Proceedings: 
Publisher: 
Institut für Computergraphik und Algorithmen
Pages: 
Year: 
2011
ISBN: 
Abstract: 
In this thesis the application of clustering algorithms for solving the Hierarchical Ring Network<br> Problem (HRNP) is investigated.<br> When the network is represented as a graph, an informal problem definition for this NPcomplete<br> problem is: Given a set of network sites (nodes) assigned to one of three layers and<br> the costs for establishing connections between sites (i.e., edge costs) the objective is to find a<br> minimum cost connected network under certain constraints that are explained in detail in the<br> thesis. The most important constraint is that the nodes have to be assigned to rings of bounded<br> size that connect the layers hierarchically.<br> The ring structure is a good compromise between the robustness of a network and the cost<br> for establishing it. It is guaranteed, that the network can continue to provide its service if one<br> network node per ring fails.<br> The basic idea in this thesis for solving this network design problem was to cluster the sites<br> with hierarchical clustering heuristics and to use the resulting hierarchy as support for the ringfinding<br> heuristics. Previous apporaches for related network design problems did not use the<br> inherent network structure in such a way. Usual approaches are based on greedy heuristics.<br> Three clustering heuristics were implemented: Girvan-Newman, K-means and Kernighan-<br> Lin. Especially the first algorithm is interesting, because it was successfully applied analyzing<br> large network structures, also in the context of internet communities.<br> For finding rings three heuristics were implemented too. Strategic variation of the maximum<br> allowed ring size helps the first heuristic to find rings using the cluster hierarchy. The second<br> heuristic finds rings by searching for paths that are connected to previously found rings. Third a<br> repair heuristic was implemented that tries to add remaining nodes to existing rings.<br> Local search heuristics are applied last to improve the solution quality.<br> To check how the clustering approach performs for solving the problem of this thesis two<br> test instance generators were implemented. One generates instances randomly and the second<br> generates instances based on the popular TSPLIB archive.<br> The evaluation of the random test instances has shown, that all three clustering heuristics<br> were able to solve those test instances, while Girvan-Newman and Kernighan-Lin found valid<br> solutions in each test run this was not possible for K-means. When Kernighan-Lin was used as<br> clustering algorithm solutions could be found faster on average, but the resulting costs where<br> slightly higher. For the TSPLIB based instances the clustering algorithms had more problems to<br> find valid solutions, but for each test instance at least one type of clustering was successful.
TU Focus: 
Computational Science and Engineering
Reference: 

R. Schuster:
"Clustering Heuristics for the Hierarchical Ring Network Problem";
Betreuer/in(nen): G. Raidl, C. Schauer; Institut für Computergraphik und Algorithmen, 2011; Abschlussprüfung: 11/2011.

Zusätzliche Informationen

Last changed: 
16.12.2011 10:30:28
Accepted: 
Accepted
TU Id: 
202034
Invited: 
Department Focus: 
Business Informatics
Author List: 
R. Schuster
Abstract German: 
In dieser Diplomarbeit wird die Anwendung von Clusteringalgorithmen untersucht, um das<br> Hierarchical Ring Network Problem (HRNP) zu lösen.<br> Wenn das Netzwerk als Graph repräsentiert ist, ist dieses NP-vollständige Problem wie folgt<br> definiert: Gegeben ist Menge von Knoten welche jeweils einer von drei Schichten zugewiesen<br> sind, und eine Kostenfunktion, welche die Verbindungskosten zwischen zwei Knoten<br> (d.h. Kantenkosten) zuweist. Gesucht ist ein zusammenhängendes Netzwerk mit minimalen<br> Gesamtkosten, wobei dieses bestimmte Struktureigenschaften zu erfu&#776;llen hat, welche im Detail<br> in der Diplomarbeit beschrieben werden. Die wichtigste dieser Eigenschaften ist, dass Knoten<br> gemäß einer hierarchischen Struktur zu größenbeschränkten Ringen verbunden werden.<br> Ringstrukturen sind ein guter Kompromiss zwischen der Verfu&#776;gbarkeit von Netzwerken und<br> deren Herstellungskosten. Die Verfu&#776;gbarkeit ist gewährleistet, solange maximal ein Knoten pro<br> Ring ausfällt.<br> Die grundlegende Idee dieser Diplomarbeit um dieses Netzwerkdesign-Problem zu lösen,<br> ist die Knoten mit Hilfe von hierarchischen Clusteringalgorithmen anzuordnen und die resultierende<br> Hierarchie fu&#776;r nachfolgende Heuristiken zu verwenden, welche die Ringe finden.<br> Vorhergehende Ansätze fu&#776;r vergleichbare Netzwerkdesign-Probleme haben die inhärente<br> Netzwerkstruktur nicht auf solche Weise genu&#776;tzt und eher Greedy-Heuristiken eingesetzt.<br> Um gu&#776;ltige Ringe zu finden, wurden drei Heuristiken implementiert. Strategisches Variieren<br> der erlaubten Ringgröße hilft der ersten Heuristik Ringe unter Benu&#776;tzung der Cluster-Hierarchie<br> zu finden. Die zweite Heuristik baut auf den in der vorherigen Schicht gefundenen Ringen auf,<br> indem sie nach gu&#776;ltigen Pfaden sucht, die an diese Ringe angeschlossen werden können. Drittens<br> wird eine Reparaturheuristik angewendet, welche versucht verbleibende Knoten zu bestehenden<br> Ringen zuzuweisen.<br> Zuletzt werden lokale Suchverfahren eingesetzt, um die Gesamtkosten zu verbessern.<br> Um zu u&#776;berpru&#776;fen, wie gut dieser Lösungsansatz funktioniert, wurden zwei Testinstanz-<br> Generatoren implementiert. Der Erste generiert Instanzen zufallsbasiert, der Zweite baut auf<br> dem bekannten TSPLIB-Archiv auf.<br> Die Evaluierung der zufallsbasierten Testinstanzen hat gezeigt, dass alle drei Heuristiken<br> sämtliche Instanzen lösen konnten, wobei Girvan-Newman und Kernighan-Lin in jedem Testlauf<br> Lösungen gefunden haben, war dies bei K-means nicht der Fall. Mit Kernighan-Lin<br> konnte im Durchschnitt schneller eine Lösung gefunden werden, aber die Gesamtkosten waren<br> bei den beiden anderen Algorithmen etwas besser. Mit den TSPLIB-basierten Testinstanzen<br> konnte nicht mit allen Clusteringalgorithmen eine Lösung erzielt werden, aber zumindest war<br> fu&#776;r jede Testinstanz mindestens ein Clustering-Verfahren erfolgreich.