A new partition-based heuristic for the Steiner tree problem in large graphs

Das Steinerbaumproblem in Graphen (STP) ist ein NP-schweres kombinatorisches Optimierungsproblem, welches sowohl aus theoretischer als auch aus praktischer Sicht relevant ist. Die Anwendungsfälle reichen vom VLSI-Design bis hin zum Lösen von wissenschaftlichen Problemen in der Bioinformatik. Beim STP sollen eine Menge an Basisknoten in einem gewichteten Graphen kostenminimal verbunden werden. Da dieses Problem sehr schwierig ist, ist es nicht immer möglich eine optimale Lösung zu finden. Problematisch sind vor allem große Instanzen, die in praktischen Anwendungen relativ häufig auftreten. In solchen Fällen bleibt oft nur die Verwendung von heuristischen Methoden. Diese sind auf die Berechnung von guten, jedoch suboptimalen Lösungen in relativ kurzer Zeit spezialisiert. In dieser Diplomarbeit wird eine neue Konstruktionsheuristik vorgestellt, die Partitionierungsmethoden nutzt, um speziell mit großen Probleminstanzen umgehen zu können. Hierzu wird eine Instanz systematisch in kleinere Instanzen zerlegt, die einfach genug sind, um sie mit einem exakten Algorithmus optimal zu lösen. Danach wird eine heuristische Lösung der ursprünglichen Instanz durch Zusammensetzen der Teillösungen erzeugt. Zur Realisierung dieses Verfahrens werden sowohl exakte und heuristische Lösungsmethoden für das STP als auch Algorithmen zur Partitionierung von Graphen kombiniert. Für die Berechnung von exakten Lösungen wird ein Branch-and-Cut Verfahren verwendet. Das zugrundeliegende ILP-Model basiert auf den bekannten directed-cut-constraints, führt jedoch zusätzlich noch die Verwendung von Knotenvariablen ein. Der zugehörigen Separierungsmethode liegen verschiedene Verbesserungen aus der Literatur zugrunde. Zur Partitionierung wird das METIS Graph Partitioning Framework verwendet. Außerdem wird ein einfacher Greedy-Algorithmus vorgestellt, welcher eine Instanz durch die Kombination mehrerer Regionen in einem Voronoi-Diagram erstellt. Die implementierten Algorithmen werden zusätzlich in einen memetischen Algorithmus integriert, darunter die vorgestellte Konstruktionsheuristik, Reduktionstests, ein Algorithmus zur Rekombination von Lösungen und Variable Neighorhood Descent. Die verwendeten Nachbarschaftsstrukturen basieren auf Steiner node insertion, Steiner node elimination, key-node elimination und key-path exchange. Alle Algorithmen werden experimentell evaluiert. Die Testinstanzen dafür stammen aus der SteinLib, welche eine Sammlung von Benchmark-Instanzen für das STP darstellt, und aus einer Gruppe aus neuen Instanzen, die Netzwerkdesignprobleme aus der Praxis beschreiben. Die Ergebnisse zeigen, dass Lösungsqualität und Laufzeit des vorgestellten Verfahrens auch für große Instanzen akzeptabel sind.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.