Memetische Algorithmen kombiniert mit Branch & Cut & Price für Netzwerk Design Probleme

01.06.2003 - 30.01.2006
Research funding project
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.

People

Project leader

Project personnel

Institute

Förderungmittel

  • FWF - Österr. Wissenschaftsfonds (National) Fonds zur Förderung der wissenschaftlichen Forschung (FWF)

Keywords

GermanEnglish
Kombinatorische Optimierungcombinatorial optimization
Netzwerk-Designnetwork design
Metaheuristikenmeta heuristics
Ganzzahlige lineare Programmierunginteger linear programming

Publications