Variable Neighborhood Search for the Partition Graph Coloring Problem

Auf gute Nachbarschaft. Aber Vorsicht: Was wie eine hochtrabend formulierte Maßnahme zur besseren Integration in einem Grätzel klingt, hat damit überhaupt nichts zu tun. Begeben Sie sich stattdessen in die Sphären der höheren technischen Mathematik. Begeben Sie sich unter die Erde, in die Glasfaserkabel, die uns unser Internet bringen sollen, und zwar möglichst schnell und ohne Kommunikationsstörungen. Jetzt sind Sie richtig, jetzt kann die „Variable Neighborhood Search“ (VNS) beginnen.

Das Thema, das Lorenz Leutgeb und Moritz Wanzenböck im Zuge ihrer Diplomarbeit in Angriff nehmen, betrifft die immer stärkeren Kommunikationsbedürfnisse, die an Anbieter/innen von Internetinfrastruktur gestellt werden. Als Alternative zum kostspieligen Ausbau des Netzes – um also nicht mit großem Aufwand neue Glasfaserkabel legen zu müssen – gibt es Formeln, die helfen sollen, die bestehenden Netze effizienter zu nutzen. Ein Professor der TU Wien schlug den beiden Nachbarschaftshelfern vor, eine Optimierung dieser Algorithmen zu versuchen.

In einem Wavelength-Division-Multiplexing-Glasfasernetzwerk mit vorab gegebenen Kommunikationsbedürfnissen reduzieren sie die Anzahl der insgesamt benötigten Wellenlängen, um Platz für weitere Übertragungskanäle zu schaffen. Das Prinzip VNS setzt darauf, dass eine Lösung, die in einer Nachbarschaft nicht mehr verbessert werden kann, in einer anderen Nachbarschaft sehr wohl noch Optimierungspotenzial besitzt. Diese neue Lösung kann dann vielleicht wieder mit einem Zug aus der ursprünglichen Nachbarschaft verbessert werden, und so weiter. Erst, wenn es besser nicht mehr geht, endet dieser systematische Prozess. Dann wird die Lösung „geschüttelt“ (ja, so heißt das wirklich!), um sie zu verfremden und wieder neue Lösungsansätze zu provozieren.

Ein auch auf die reale Welt übertragbares Mittel zur guten Zusammenarbeit! In kleinerem Testrahmen bringt der neue Algorithmus schon vielversprechende Ergebnisse. Jetzt gilt es nur noch, die sogenannte Tabu-Suche, die bei größeren Netzwerken derzeit die erfolgreichste ist, zu unterbieten.