@misc{Raack, type = {Master Thesis}, author = {Raack, Christian}, title = {Employing Mixed-Integer Rounding in Telecommunication Network Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10023}, school = {Zuse Institute Berlin (ZIB)}, abstract = {In dieser Diplomarbeit werden grundlegende Probleme der kostenoptimalen Dimensionierung von Telekommunikationsnetzwerken untersucht. Diese werden als lineare gemischt ganzzahlige Programme formuliert, wobei sich in der Modellierung auf die Konzepte Routing und Kapazit{\"a}tszuweisung beschr{\"a}nkt wird. Es werden parallel drei {\"u}bliche, aus der Praxis motivierte M{\"o}glichkeiten behandelt, die auf gerichteten oder ungerichteten Kanten eines Netzwerkes installierte Kapazit{\"a}t zu nutzen. Diese unterscheiden wir als DIrected, BIdirected und UNdirected. Die studierten Probleme treten als Relaxierungen vieler realistischer Fragestellungen der Netzwerkoptimierung auf. Sie enthalten elementare Strukturen, deren Studium ausschlaggebend ist f{\"u}r das Verst{\"a}ndnis komplexerer Modelle. Letztere k{\"o}nnen zus{\"a}tzliche Erfordernisse ber{\"u}cksichtigen, wie zum Beispiel die Ausfallsicherheit von Netzwerken. Zur L{\"o}sung solcher NP-schweren Optimierungsprobleme werden erfolgreich Branch \& Bound und Schnittebenenverfahren kombiniert (Branch \& Cut). F{\"u}r die Wirksamkeit dieser Algorithmen ist es sehr n{\"u}tzlich, m{\"o}glichst genaue Kenntnisse der Struktur der Seitenfl{\"a}chen der zugrundeliegenden Polyeder zu haben, welche die konvexe H{\"u}lle der L{\"o}sungsmenge beschreiben. Es sind starke g{\"u}ltige Ungleichungen zu finden, welche hochdimensionale Seitenfl{\"a}chen oder sogar Facetten definieren. Diese sollten zudem schnell separiert werden k{\"o}nnen und die numerische Stabilit{\"a}t der Algorithmen m{\"o}glichst nicht beeinflussen. Diese Arbeit besch{\"a}ftigt sich im Wesentlichen mit der sehr allgemeinen Rundungstechnik Mixed- Integer Rounding (MIR) zur Verst{\"a}rkung g{\"u}ltiger Ungleichungen unter Verwendung der Ganzzahligkeitsnebenbedingungen. Es wird eine MIR-Prozedur motiviert, bestehend aus den Schritten Aggregieren, Substituieren, Komplementieren und Skalieren, welche durch Ausnutzung der Struktur der gegebenen Parameter zu einer g{\"u}ltigen Basisungleichung f{\"u}hrt, die dann durch MIR eine starke und oft facetten-induzierende Ungleichung gibt. Es werden verschieden Klassen solcher Ungleichungen untersucht und auf ihre Praxistauglichkeit beim Einsatz in Branch \& Cut-Verfahren getestet. Nach einer kurzen Einf{\"u}hrung werden in Kapitel 2 die f{\"u}r uns in dieser Diplomarbeit relevanten Probleme definiert. Kapitel 3 gibt eine ausf{\"u}hrliche {\"U}bersicht {\"u}ber die Technik MIR.Wir besch{\"a}ftigen uns vor allen Dingen mit den Begriffen Superadditivit{\"a}t und Lifting und behandeln Aspekte wie Numerik und beschr{\"a}nkte Variablen. Kapitel 4 und Kapitel 5 umfassen Untersuchungen zu so genannten cut sets. Diese Polyeder werden durch Schnitte in Netzwerken definiert und relaxieren die von uns behandelten Probleme. Haupts{\"a}chlich durch MIR entwickeln wir sowohl neue als auch bekannte Klassen von facetten-definierenden Ungleichungen f{\"u}r cut sets, wobei strukturelle Unterschiede herausgearbeitet werden, die durch die drei verschiedenen Typen der Kapzit{\"a}tsbereitstellung und durch beschr{\"a}nkte Variablen entstehen. Als ein zentrales Resultat wird bewiesen unter welchen Bedingungen facetten-induzierende Ungleichungen f{\"u}r cut sets auch Facetten der zugeh{\"o}rigen relaxierten Polyeder sind. Im Kapitel 6 geben wir weitere Typen von MIR-Ungleichungen an, die auf anderen Netzwerkstrukturen basieren und weisen ferner auf offene Fragen sowie interessante Ideen hin. Das Kapitel 7 widmet sich schließlich der Entwicklung und Implementation von Separationsalgorithmen. Wir testen einige der entwickelten Ungleichungsklassen mit Hinblick auf Ihre Wirksamkeit zur L{\"o}sung von realistischen Problemen der Netzwerkdimensionierung aus der Telekommunikation und diskutieren die Ergebnisse.}, language = {de} }