Memetische Algorithmen kombiniert mit Branch & Cut & Price

Wir betrachten hier einige Netzwerk-Design Probleme, die beispielsweise in den Bereichen Telekommunikation, Energieversorgung oder Fernwärme eine schwierige Herausforderung darstellen. Das gemeinsame Ziel in diesen Problemen ist es, eine möglichst kostengünstige Menge von Verbindungen zwischen Knoten zu finden, um ein Netzwerk aufzubauen, das spezielle Randbedingugnen erfüllt. Im gradbeschränkten Spannbaumproblem, beispielsweise, ist die Anzahl der Verbindungen, die an einem Knoten angebracht werden dürfen, beschränkt und das Netzwerk muss baumförmige Struktur haben und alle Knoten verbinden. In einem anderen Problem sind Kommunikationsbedürfnisse gegeben und die Verbindungen haben Kapazitätsbeschränkungen. Wir betrachten auch Probleme, bei denen ein bestehendes Netzwerk mit zusätzlichen Verbindungen so erweitert werden soll, dass es im Falle eines Ausfalls einzelner Knoten oder Verbindungen nicht zerfällt. Alle diese Probleme sind NP-schwierig, was für die Praxis bedeutet, dass große Instanzen normalerweise nicht beweisbar optimal gelöst werden können. In der Vergangenheit haben sich zwei besonders effektive Optimierungsansätze für derartige Problemstellungen bewährt. Auf der einen Seite sind das exakte Verfahren basierend auf Branch-and-Bound und linearer Programmierung. Für leichtere oder nicht zu große Instanzen liefern diese Techniken oft beweisbar optimale Lösungen. Bezogen auf unsere Netzwerk-Design Probleme ist Branch-and-Cut-and-Price (BCP) einer der effektivsten Algorithmen dieser Kategorie. Auf der anderen Seite haben sich evolutionäre Algorithmen kombiniert mit problemspezifischen Heuristiken, lokaler Suche und spezialisierten Operatoren -- sogenannte Memetische Algorithmen (MAs) -- bewährt, um Lösungen hoher Qualität für große und schwierige Instanzen zu finden. In diesem Projekt setzen wir die Entwicklung effektiver MAs und BCP-Algorithmen für die betrachteten Netzwerk-Design Probleme fort. Zusätzlich untersuchen wir verschiedene Ansätze, um "das Beste der beiden Welten" zu kombinieren. Durch den Austausch guter Lösungen und anderer wertvoller Informationen können beide Verfahren profitieren. Synergieeffekte machen den kombinierten MA/BCP-Ansatz effektiver als jedes einzelne Verfahren.

In diesem Projekt wurden verschiedene kombinatorische Netzwerk-Design-Probleme betrachtet, welche eine große Herausforderung in Bereichen wie Telekommunikation, Energielieferung und Fernwärme darstellen. Das gemeinsame Ziel in diesen Problemen ist, eine kostengünstigste Menge von Verbindungen zwischen Knotenpunkten zu finden, sodass ein Netzwerk geschaffen wird, welches spezielle Anforderungen erfüllt. Weiters wurden schwierige Probleme aus den Bereichen der zweidimensionalen Pack- bzw. Verschnittoptimierung und ein aus der Automobilindustrie kommendes Planungsproblem betrachtet. Alle diese Probleme sind NP-schwer, was bedeutet, dass es im Allgemeinen sehr schwierig ist größere Instanzen in der Praxis in akzeptabler Rechenzeit zu lösen. In der Vergangenheit haben sich zwei besonders effektive Optimierungsansätze für derartige Problemstellungen bewährt. Auf der einen Seite sind das exakte Verfahren basierend auf Branch-and-Bound und linearer Programmierung. Für leichtere oder nicht zu große Instanzen liefern diese Techniken oft beweisbar optimale Lösungen. Bezogen auf die von uns betrachteten Probleme gehören Branch-and-Cut, Branch-and-Price und Branch-and-Cut-and-Price (BCP) zu den bewährtesten Algorithmen dieser Art. Auf der anderen Seite haben sich Metaheuristiken, im Speziellen evolutionäre Algorithmen kombiniert mit problemspezifischen Heuristiken, lokaler Suche und spezialisierten Operatoren sogenannte Memetische Algorithmen (MAs) bewährt, um Lösungen hoher Qualität für große und schwierige Instanzen in relativ kurzer Zeit zu finden. In diesem Projekt haben wir die Entwicklung leistungsfähiger MAs und BCP Algorithmen für die betrachteten Probleme erfolgreich weitergeführt. Zusätzlich wurde an unterschiedlichen Ansätzen zur Kombination "des Besten aus beider Welten" geforscht. Die Ergebnisse dokumentieren, dass derartige kombinierte MA/BCP-Ansätze auf Grund verschiedener Synergieeffekte oft deutlich effektiver sind als der MA bzw. das BCP alleine. Derartige Kombinationen können grob in kollaborative und integrative Methoden eingeteilt werden. Kollaborative Ansätze können sequentieller oder paralleler Natur sein, während bei integrativen Methoden das BCP Teilaufgaben im MA lösen kann oder vice versa. Die entwickelten Algorithmen wurden einerseits für die betrachteten Probleme spezialisiert um möglichst gute Ergebnisse zu erhalten, die Grundprinzipien jedoch sind allgemeiner gültig und können auch auf viele andere schwierige kombinatorische Optimierungsaufgaben angewandt werden.