Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-239
Main Title: Mathematische Modellierung und Lösung von Optimierungsproblemen bei der Planung von Telefonnetzen
Translated Title: Mathematical modeling and solution of optimization problems arising in telephone network planning
Author(s): Stolle, Hermann
Advisor(s): Grötschel, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: German
Language Code: de
Abstract: Diese Doktorarbeit behandelt praktische Probleme, die mit der Planung von Telefonnetzwerken zusammenhängen. In einem speziellen Fall in der Arbeit sollen Endverteiler eines Stadtbereichs an Bereichsverteiler mit Kabeln und weiteren Verteiler angeschlossen werden. Die Kabel sind in Tiefbau zu verlegen. Die Länge der Kabelverbindung ist beschränkt. Gesucht ist ein Netzwerkentwurf, der alle diese Nebenbedingungen erfüllt und dessen Kosten minimal sind. Die Modellierung dieses praktischen Prolems wird ausführlich diskutiert. Ein mathematisches Optimierungsproblem in gerichteten Graphen, das Kabelproblem, wird für dessen Lösung vorgeschlagen. Das Kabelproblem ist ein NP-schweres Optimierungsproblem. Es enthält das Steinerbaum-Problem in gerichteten Graphen als Spezialfall. Wir untersuchen eine Generalisierung des Kabelproblems, das Netzproblem, um Resultate zu erzielen, die auch für Modifikationen des Kabelproblems genutzt werden können. Wir beschreiben Problemreduzierungen und -transformationen und führen ein ganzzahliges lineares Programm für das Netzproblem ein. Verschiedene LP-Relaxierungen dieses ganzzahligen Programms werden verglichen in Bezug auf ihre Performance in einem Branch-and-Cut-and-Price-Verfahren für das Netzproblem. Die polyedrische Untersuchung des Netzproblems wird in Bezug gesetzt zu den praktischen Erfordernissen des Branch-and-Cut-and-Price-Verfahrens. Schließlich werden verschiedene ganzzahlige und lineare Programme für das Netzproblem in Bezug gesetzt und so verglichen. Die Verfahren zur Lösung des Kabelproblems bestehen aus Problemreduktionen, primalen und dualen Verbesserungsheuristiken und exakten Branch-and-Cut-and-Price-Verfahren. Die Verfahren werden auf Instanzen des realen Planungsproblems für Telefonnetzwerke angewandt. Die Resultate für diese Instanzen sind sehr erfreulich. Eine zweite Anwendung sind Steinerbaum-Probleme in Graphen, die bei dem Entwurf von elektronischen Schaltkreisen (VLSI-Design) auftreten. Für viele Instanzen einer Steinerbaum-Benchmark ist die Performance unserer Verfahren besser als die der besten in der Literatur beschriebenen Verfahren. Dies zeigt, daß unserer genereller Ansatz für Kabelprobleme auch auf praktische Probleme dieses spezifischeren Typs anwendbar sind.
This thesis addresses practicle problems that are related to the planning of telephone networks. In a specific case investigated in the thesis, end distribution points (located in a district of a town) are to be connected to remote distribution points by cables and further distributors. The cables have to be placed in trenches. The length of the cable connections is limited. A design has to be found that satisfies all side constraints and minimizes the costs involved. The modeling procedure of this practicle problem is discussed in depth. A mathematical optimization problem in directed graphs, the cable problem, is proposed for its solution. The cable problem is an NP-hard optimization problem. It contains the Steiner tree problem in directed graph as a special case. We investigate a generalization of the cable problem, the net problem, with the aim to obtain results that can also be utilized for modifications of the cable problem. We describe problem reductions and transformations and introduce an integer linear program formulation for the net problem. Several LP-relaxations of this integer program are compared with respect to their performance in a branch-and-cut-and-price-procedure to solve the net problem. The polyhedral investigation of the net problem is also related to the practicle requirements in a branch-and-cut-and-price-procedure. Finally different integer and linear programs for the net problem are related to each other and thus compared. The algorithms for solving the cable problem consist of problem reductions, primal and dual improvement heuristics, a Lagrangian heuristic and exact branch-and-cut-and-price-procedures. The algorithms are applied to instances of real world planning problems of telephone networks. The results for these instances are very encouraging. A second application are Steiner tree problems in graphs arising in the design of electronic circuits (VLSI-design). For many instances of a Steiner tree benchmark suite, our algorithms perform better than the best known algorithms discussed in the literature. This shows that our general framework for cable problems is applicable to practicle problems of this more specific type as well.
URI: urn:nbn:de:kobv:83-opus-1419
http://depositonce.tu-berlin.de/handle/11303/536
http://dx.doi.org/10.14279/depositonce-239
Exam Date: 16-Jun-2000
Issue Date: 15-Sep-2000
Date Available: 15-Sep-2000
DDC Class: 510 Mathematik
Subject(s): Ganzzahlige Lineare Programmierung
Netzwerk-Entwurf
Telekommunikation
Usage rights: Terms of German Copyright Law
Appears in Collections:Fakultät 2 Mathematik und Naturwissenschaften » Publications

Files in This Item:
File Description SizeFormat 
Dokument_46.pdf3.18 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.