Bibliographic Metadata

Title
Solving two network design problems by mixed integer programming and hybrid optimization methods / Markus Leitner
Additional Titles
Übers. d. Hauptsacht.: Ganzzahlige lineare Programmierung und hybride Optimierungsverfahren zur Lösung von zwei Netzwerkdesignproblemen
AuthorLeitner, Markus
CensorRaidl, Günther ; Pferschy, Ulrich
Published2010
DescriptionXII, 165 S. : graph. Darst.
Institutional NoteWien, Techn. Univ., Diss., 2010
Annotation
Zsfassung in dt. Sprache
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)kombinatorische Optimierung / Netzwerkdesign / ganzzahlige lineare Programmierung / Branch&Cut&Price / Lagrange Relaxierung / Metaheuristiken / Hybridalgorithmen
Keywords (EN)combinatorial optimization / network design / integer linear programming / branch-and-cut-and-price / Lagrange relaxation / metaheuristics / hybrid algorithms
Keywords (GND)Kombinatorische Optimierung / Netzwerk / Design / NP-hartes Problem / Ganzzahlige Optimierung / Branch-and-Cut-Methode / Branch-and-Price-Methode / Metaheuristik / Effizienter Algorithmus
URNurn:nbn:at:at-ubtuw:1-36359 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Solving two network design problems by mixed integer programming and hybrid optimization methods [0.75 mb]
Links
Reference
Classification
Abstract (German)

Diese Dissertation behandelt Optimierungsverfahren für zwei NP-schwere kombinatorische Optimierungsprobleme, mit welchen mögliche Strategien zur Erweiterung von Telekommunikationsnetzwerken modelliert werden können. Aufgrund eines höheren Bandbreitenbedarfs von Kunden müssen Telekommunikationsfirmen ihre Netze erweitern. Im Allgemeinen sind Kunden jedoch nicht bereit wesentlich höhere Preise für schnellere Breitbandanschlüsse zu bezahlen. Aus diesem Grund sind gute Algorithmen zur kosteneffizienten Planung derartiger Netzwerke von entscheidender Bedeutung.

Das bmax-Survivable Network Design Problem (bmax-SNDP) betrachtet das Problem der effizienten Erweiterung eines bestehenden Netzes zur Versorgung neuer Kunden. Neben sogenannten Typ-1 Kunden mit nur einfachen Anbindungsanforderungen werden Typ-2 Kunden berücksichtigt, welche eine zuverlässigere Verbindung benötigen. Für diese muss Konnektivität auch im Fall eines Fehlers eines Kabels oder eines Routers garantiert werden.

Bei bmax-SNDP kann diese Redundanzanforderung jedoch relaxiert werden.

In diesem Fall darf das letzte Stück der Anbindung nichtredundant ausgeführt werden. Dieses darf jedoch eine Gesamtlänge von bmax nicht überschreiten.

Es werden zwei auf gemischt-ganzzahliger linearer Programmierung beruhende Modelle vorgeschlagen, welche mittelgroße Probleminstanzen beweisbar optimal lösen. Diese werden sowohl theoretisch also auch mittels computationaler Tests mit existierenden Verfahren verglichen. Weiters werden ein auf Lagranger Relaxierung basierender hybrider Optimierungsansatz sowie metaheuristische Methoden zur näherungsweisen Lösung von sehr großen Instanzen vorgeschlagen. Die erzielten Testergebnisse belegen die Effektivität der vorgestellten Lösungsansätze.

Häufig ist ein Kompromiss zwischen der für Kunden verfügbaren Bandbreite und den Kosten für das Netzwerk nötig. In solchen Fällen wird das Netz nicht bis zu den Kunden, sondern nur bis zu Übergabepunkten errichtet, welche das neue und alte Netz miteinander koppeln.

Derartige Szenarien können als Varianten des Connected Facility Location Problems (ConFL) modelliert werden, bei dem eine Menge an Facilities mit entsprechend zugewiesenen Kunden ausgewählt und miteinander verbunden werden muss.

Der zweite Teil dieser Arbeit beschäftigt sich mit dem Capacitated Connected Facility Location Problem (CConFL), welches ConFL um wichtige Nebenbedingungen erweitert. Es werden vier auf gemischt-ganzzahliger linearer Programmierung beruhende Modelle vorgestellt, welche beweisbar optimale Lösungen für CConFL berechnen. Diese werden im Anschluss anhand ihrer zugrundeliegenden Polyeder theoretisch miteinander verglichen.

Weiters wird ein auf Lagranger Relaxierung basierender Ansatz vorgestellt, welcher im Anschluss mit lokaler Suche sowie very large scale neighborhood search hybridisiert wird.

Die Ergebnisse der durchgeführten computationalen Studie zeigen klare Vorteile für zwei der vorgestellten Lösungsansätze.

Abstract (English)

This thesis considers optimization methods for two NP-hard combinatorial optimization problems suitable to model the extension of real world communication networks. Nowadays, telecommunication companies need to upgrade and extend existing networks due to rising bandwidth requirements of customers. Customers are, however, usually not willing to pay significantly more than for existing lower bandwidth connections. Thus good algorithms for finding cost-efficient network layouts are crucial. The bmax-Survivable Network Design Problem (bmax-SNDP) aims to efficiently extend an existing network to supply new customers. Here, two sets of customers are given. Standard customers which are denoted as type-1 customers need to be connected by simple routes, while type-2 customers need a more reliable connection. For the latter, connectivity needs to be ensured even when a single link or routing node fails.

Furthermore, these redundancy requirements are occasionally relaxed by allowing a connection via a final non-redundant branch line that does not exceed a certain length bmax. We present new mixed integer programming models for solving medium sized instance of bmax-SNDP to proven optimality. These are compared to existing ones theoretically as well as by a computational study.

Furthermore, a new hybrid optimization approach based on Lagrangian relaxation as well as metaheuristic methods for approximately solving large instances are described. Computational results demonstrate the efficiency of the proposed solution approaches. Often a compromise between the bandwidth offered to individual customers and the resulting network construction costs has to be made. In such situations the infrastructure is typically extended to so-called mediation points that bridge the high-bandwidth network with an older lower-bandwidth network. Such scenarios can be modeled as variants of the Connected Facility Location Problem (ConFL) where new facilities, which correspond to the above mentioned mediation points, need to be installed and connected with each other.

Furthermore, customer nodes need to be assigned to them. The Capacitated Connected Facility Location Problem (CConFL), which is addressed in the second part of this thesis, extends ConFL by considering additional real world constraints.

We present four new mixed integer programming models for solving instances of CConFL to proven optimality. Subsequently, a theoretical comparison of the polyhedra corresponding to these four models is given.

Furthermore, a Lagrangian relaxation method which is hybridized with local search and very large scale neighborhood search is described. The results obtained from a computational study indicate clear advantages for two of the proposed solution methods.

Stats
The PDF-Document has been downloaded 35 times.