Eingang zum Volltext
Lizenz
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:kobv:83-opus-22754
URL: http://opus.kobv.de/tuberlin/volltexte/2009/2275/
Orlowski, Sebastian
Schichten, sogenannten Layern, die eng miteinander verknüpft
sind. Ein Beispiel für ein solches Netz ist ein IP-Kernnetz,
bei dem Verbindungen zwischen Internet-Routern durch Lichtwege
in einem zugrundeliegenden optischen Glasfasernetz realisiert werden. Um
sicherzustellen, dass das Netz in jeder Situation alle anfallenden
Kommunikationsbedarfe routen kann, müssen die Abhängigkeiten zwischen
den verschiedenen Schichten schon bei der Planung des Netzes
berücksichtigt werden. Dies ist vor allem dann von Bedeutung, wenn
Verbindungen in einer Schicht gegen Kabel- oder Geräteausfälle
in einer anderen Schicht geschützt werden müssen. Der traditionelle
sequentielle Ansatz, bei dem eine Schicht nach der anderen optimiert
wird, kann solche Abhängigkeiten nicht ausreichend berücksichtigen.
Dies ist nur mit einem integrierten Planungsansatz möglich, bei dem
mehrere Schichten gemeinsam geplant werden.
Diese Arbeit behandelt mathematische Modelle und Lösungsverfahren für
die integrierte Optimierung zweier zusammenhängender Netzschichten mit
Ausfallsicherheitsanforderungen. Wir stellen ein
Multi-layer-Netzplanungsproblem vor, das in mehreren Technologien
auftritt, und modellieren es in Form von gemischt-ganzzahligen
Optimierungsmodellen (MIPs). Diese Modelle decken viele praktisch
relevante Nebenbedingungen aus verschiedenen Technologien ab. Im
Gegensatz zu vorherigen Modellen aus der Literatur können sie zur
Lösung großer ausfallsicherer Zwei-layer-Netze verwendet werden. Im
Zusammenhang damit diskutieren wir verschiedene Modellierungsoptionen
für wesentliche Teile eines Multi-layer-Netzes.
Wir lösen unsere Modelle mit einem Branch-and-cut-and-price-Verfahren
in Verbindung mit verschiedenen problemspezifischen Techniken.
Dies umfasst Presolving-Techniken zur Reduktion der Problemgröse,
kombinatorische und MIP-basierte Primalheuristiken zur Berechnung von
Netzkonfigurationen, spezielle Schnittebenen für Ausfallsicherheit
über mehrere Schichten hinweg zur Verbesserung der unteren Schranke an
die optimalen Netzkosten, sowie Spaltengenerierung zur dynamischen
Erzeugung von Flussvariablen während des Algorithmus. Darüber hinaus
entwickeln wir Verfahren, um Rechnungen mit einem Benders-Dekompositionsansatz
zu beschleunigen.
Die entwickelten Techniken werden verwendet, um große ausfallsichere
Zwei-layer-Netze mit Methoden der linearen und ganzzahligen Optimierung
zu planen. Wir evaluieren unsere Techniken auf realistischen
Testinstanzen mit bis zu 67 Netzknoten und
Ausfallsicherheitsanforderungen und berechnen mit ihrer Hilfe gute
Netzkonfigurationen mit Qualitätsgarantien. Die meisten unserer
Testinstanzen mit bis zu 17 Knoten können wir nahezu optimal
lösen. Darŭber hinaus können wir selbst für große ausfallsichere
Netze Lösungen und aussagekräftige untere Schranken für die
optimalen Netzkosten berechnen, was bisher nicht möglich war.
technologically different subnetworks, so-called layers, which
are strongly interdependent. For example, one layer may correspond to
an Internet (IP) backbone network whose links are realized by lightpath
connections in an underlying optical fiber layer. To ensure that the
network can fulfill its task of routing all communication requests,
the inter-layer dependencies have to be taken into account already in
the planning phase of the network. This is particularly important with
survivability constraints, where connections in one layer have to be
protected against cable cuts or equipment failures in another
layer. The traditional sequential planning approach where one layer is
optimized after the other cannot properly take care of the inter-layer
dependencies; this can only be achieved with an integrated planning of
several network layers at the same time.
This thesis provides mathematical models and algorithmic techniques for
the integrated optimization of two network layers with survivability
constraints. We describe a multi-layer network design problem which
occurs in various technologies, and model it mathematically using
mixed-integer programming (MIP) formulations. The presented models cover
many important practical side constraints from different technological
contexts. In contrast to previous models from the literature, they can
be used to design large two-layer networks with survivability
requirements. We discuss modeling alternatives for various aspects of a
multi-layer network and compare different routing formulations under
multi-layer survivability constraints.
We solve our models using a branch-and-cut-and-price approach with
various problem-specific enhancements. This includes a presolving technique based on linear programming to
reduce the problem size, combinatorial and sub-MIP-based primal
heuristics to compute feasible network configurations, cutting planes
which take the multi-layer survivability constraints into account to
improve the lower bound on the optimal network cost, and column
generation to generate flow variables dynamically during the algorithm.
We develop techniques to speed up computations in a Benders
decomposition approach and compare this approach to the standard
formulation with a single MIP.
We use the developed techniques to design large survivable two-layer
networks by means of linear and integer programming methods. On
realistic test instances with up to 67 network nodes and survivability
constraints, we investigate the algorithmic impact of our techniques and
show how to use them to compute good network configurations with quality
guarantees. Most of the smaller test instances with up to 17 nodes can
be solved to near-optimality. Moreover, we can compute feasible
solutions and dual bounds even for large networks with survivability
constraints, which has not been possible before.
URN: urn:nbn:de:kobv:83-opus-22754
URL: http://opus.kobv.de/tuberlin/volltexte/2009/2275/
Orlowski, Sebastian
Optimal Design of Survivable Multi-layer Telecommunication Networks
Optimales Design ausfallsicherer Multi-layer-Telekommunikationsnetze
| pdf-Format: |
|
Kurzfassung in Deutsch
Telekommunikationsnetze bestehen aus verschiedenen technologischenSchichten, sogenannten Layern, die eng miteinander verknüpft
sind. Ein Beispiel für ein solches Netz ist ein IP-Kernnetz,
bei dem Verbindungen zwischen Internet-Routern durch Lichtwege
in einem zugrundeliegenden optischen Glasfasernetz realisiert werden. Um
sicherzustellen, dass das Netz in jeder Situation alle anfallenden
Kommunikationsbedarfe routen kann, müssen die Abhängigkeiten zwischen
den verschiedenen Schichten schon bei der Planung des Netzes
berücksichtigt werden. Dies ist vor allem dann von Bedeutung, wenn
Verbindungen in einer Schicht gegen Kabel- oder Geräteausfälle
in einer anderen Schicht geschützt werden müssen. Der traditionelle
sequentielle Ansatz, bei dem eine Schicht nach der anderen optimiert
wird, kann solche Abhängigkeiten nicht ausreichend berücksichtigen.
Dies ist nur mit einem integrierten Planungsansatz möglich, bei dem
mehrere Schichten gemeinsam geplant werden.
Diese Arbeit behandelt mathematische Modelle und Lösungsverfahren für
die integrierte Optimierung zweier zusammenhängender Netzschichten mit
Ausfallsicherheitsanforderungen. Wir stellen ein
Multi-layer-Netzplanungsproblem vor, das in mehreren Technologien
auftritt, und modellieren es in Form von gemischt-ganzzahligen
Optimierungsmodellen (MIPs). Diese Modelle decken viele praktisch
relevante Nebenbedingungen aus verschiedenen Technologien ab. Im
Gegensatz zu vorherigen Modellen aus der Literatur können sie zur
Lösung großer ausfallsicherer Zwei-layer-Netze verwendet werden. Im
Zusammenhang damit diskutieren wir verschiedene Modellierungsoptionen
für wesentliche Teile eines Multi-layer-Netzes.
Wir lösen unsere Modelle mit einem Branch-and-cut-and-price-Verfahren
in Verbindung mit verschiedenen problemspezifischen Techniken.
Dies umfasst Presolving-Techniken zur Reduktion der Problemgröse,
kombinatorische und MIP-basierte Primalheuristiken zur Berechnung von
Netzkonfigurationen, spezielle Schnittebenen für Ausfallsicherheit
über mehrere Schichten hinweg zur Verbesserung der unteren Schranke an
die optimalen Netzkosten, sowie Spaltengenerierung zur dynamischen
Erzeugung von Flussvariablen während des Algorithmus. Darüber hinaus
entwickeln wir Verfahren, um Rechnungen mit einem Benders-Dekompositionsansatz
zu beschleunigen.
Die entwickelten Techniken werden verwendet, um große ausfallsichere
Zwei-layer-Netze mit Methoden der linearen und ganzzahligen Optimierung
zu planen. Wir evaluieren unsere Techniken auf realistischen
Testinstanzen mit bis zu 67 Netzknoten und
Ausfallsicherheitsanforderungen und berechnen mit ihrer Hilfe gute
Netzkonfigurationen mit Qualitätsgarantien. Die meisten unserer
Testinstanzen mit bis zu 17 Knoten können wir nahezu optimal
lösen. Darŭber hinaus können wir selbst für große ausfallsichere
Netze Lösungen und aussagekräftige untere Schranken für die
optimalen Netzkosten berechnen, was bisher nicht möglich war.
Kurzfassung in Englisch
Telecommunication transport networks consist of a stack oftechnologically different subnetworks, so-called layers, which
are strongly interdependent. For example, one layer may correspond to
an Internet (IP) backbone network whose links are realized by lightpath
connections in an underlying optical fiber layer. To ensure that the
network can fulfill its task of routing all communication requests,
the inter-layer dependencies have to be taken into account already in
the planning phase of the network. This is particularly important with
survivability constraints, where connections in one layer have to be
protected against cable cuts or equipment failures in another
layer. The traditional sequential planning approach where one layer is
optimized after the other cannot properly take care of the inter-layer
dependencies; this can only be achieved with an integrated planning of
several network layers at the same time.
This thesis provides mathematical models and algorithmic techniques for
the integrated optimization of two network layers with survivability
constraints. We describe a multi-layer network design problem which
occurs in various technologies, and model it mathematically using
mixed-integer programming (MIP) formulations. The presented models cover
many important practical side constraints from different technological
contexts. In contrast to previous models from the literature, they can
be used to design large two-layer networks with survivability
requirements. We discuss modeling alternatives for various aspects of a
multi-layer network and compare different routing formulations under
multi-layer survivability constraints.
We solve our models using a branch-and-cut-and-price approach with
various problem-specific enhancements. This includes a presolving technique based on linear programming to
reduce the problem size, combinatorial and sub-MIP-based primal
heuristics to compute feasible network configurations, cutting planes
which take the multi-layer survivability constraints into account to
improve the lower bound on the optimal network cost, and column
generation to generate flow variables dynamically during the algorithm.
We develop techniques to speed up computations in a Benders
decomposition approach and compare this approach to the standard
formulation with a single MIP.
We use the developed techniques to design large survivable two-layer
networks by means of linear and integer programming methods. On
realistic test instances with up to 67 network nodes and survivability
constraints, we investigate the algorithmic impact of our techniques and
show how to use them to compute good network configurations with quality
guarantees. Most of the smaller test instances with up to 17 nodes can
be solved to near-optimality. Moreover, we can compute feasible
solutions and dual bounds even for large networks with survivability
constraints, which has not been possible before.
| Freie Schlagwörter (deutsch): | Telekommunikationsnetze , Planung von Multi-layer-Netzen , Ausfallsicherheit , gemischt-ganzzahlige Optimierung , Branch-and-cut-and-price | |
| Freie Schlagwörter (englisch): | telecommunication networks , survivable multi-layer network design , mixed-integer programming , branch-and-cut-and-price | |
| Institut: | Institut für Mathematik | |
| Fakultät: | Fakultät II - Mathematik und Naturwissenschaften | |
| DDC-Sachgruppe: | Mathematik | |
| Dokumentart: | Dissertation | |
| Hauptberichter: | Grötschel, Martin (Prof. Dr.) | |
| Sprache: | Englisch | |
| Tag der mündlichen Prüfung: | 04.05.2009 | |
| Erstellungsjahr: | 2009 | |
| Publikationsdatum: | 06.07.2009 | |
| Lizenz: | Standardlizenz eingeschränkt: Typ CC by-nc-nd - Namensnennung erforderlich | Kommerziell nein | Weiterbearbeitung nein | PoD ja |
