[Back]


Doctor's Theses (authored and supervised):

M. Leitner:
"Solving Two Network Design Problems by Mixed Integer Programming and Hybrid Optimization Methods";
Supervisor, Reviewer: G. Raidl, U. Pferschy; Institut für Computergraphik und Algorithmen, 2010; oral examination: 2010-06-16.



English abstract:
This thesis considers two NP-hard combinatorial optimization problems (COPs)from the domain of network design. Network design problems (NDPs) arise in a multitude
of real world applications such as the design of telecommunication networks.
The NDPs addressed in this thesis are suitable to model certain real-world scenarios
occurring in the extension of communication networks on the last mile. Nowadays,telecommunication companies need to upgrade and extend existing networks due to
the rising bandwidth requirements of customers. Customers are, however, not usually
willing to pay signi cantly more than for existing lower bandwidth connections.
Thus good algorithms for nding cost-efficient network layouts are crucial.
The bmax-Survivable Network Design Problem (bmax-SNDP), which allows for modeling ber-to-the-home scenarios, 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 or C1 customers need to be connected by simple routes,
while type-2 (or C2) customers need a more reliable connection. For the latter, connectivity
needs to be ensured even when a single link or routing node fails, i.e. pairs of node-disjoint paths are required. Furthermore, these redundancy requirements
are occasionally relaxed by allowing a connection via a nal non-redundant branch
line that does not exceed a certain length bmax. In this thesis, two di erent variants
with respect to the objective of bmax-SNDP are considered. In the operative planning
task (OPT) a cheapest network feasibly connecting all given customers needs to
be identi ed, while in the strategic simulation task (SST) return-on-investments are
additionally considered. Here, the objective is to identify a most pro table solution
supplying only a subset of all customers.
Two mixed integer programming models, which can be solved by branch-and-price, are discussed and compared to existing approaches theoretically as well as by a
computational study. They are suitable for solving small and medium sized instances
of bmax-SNDP to proven optimality. One main contribution within this section is
the usage of alternative dual-optimal solutions in the pricing subproblem, which
signi cantly accelerates the solution of the linear relaxation of both models.
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.
Especially in rural districts covering larger areas by ber optic networks often does
not pay o economically. Thus, a compromise between the bandwidth o ered to individual
customers and the resulting network construction costs has to be made. In
such situations the ber-optic infrastructure is typically extended to so-called mediation
points that bridge the high-bandwidth network with an older lower-bandwidth
network, i.e. ber-to-the-curb. From an optimization point of view 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 to 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 such as those imposed by the individual bandwidth demands of customers and given maximum assignable demands for each potential facility location (mediation
point). Furthermore, CConFL aims to determine a most pro table network
instead of simply minimizing the resulting costs while mandatorily supplying all customers.
Four new mixed integer programming models for solving instances of CConFL to proven optimality are presented and their solution is discussed in detail. 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.

German abstract:
Diese Dissertation behandelt zwei NP-schwere kombinatorische Optimierungsprobleme aus dem Bereich Netzwerkdesign. Derartige Netzwerkdesignprobleme treten in vielen praktischen Anwendungen, wie etwa dem Design von Telekommunikationsnetzen,
auf. Die beiden in dieser Arbeit behandelten Probleme erlauben
die Modellierung von Szenarien welche beispielsweise bei der Planung von Glasfasernetzwerken auftreten. Aufgrund gestiegener Kundenanforderungen hinsichtlich verfügbarer Bandbreite sind Telekommunikations rmen gezwungen ihre Netze zu
erweitern bzw. existierende Kupferverbindungen sukzessive duch Glasfaser zu ersetzen.
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 die Aufgabe der effizienten Erweiterung von Fiber-to-the-home Netzwerken. Hierbei sind neben sogenannten Standardkunden mit einfachen Anbindungsanforderungen, welche auch als Typ-1 oder C1 Kunden bezeichnet werden, zusätzlich Typ-2 (oder C2) Kunden
gegeben. Für diese muss die Verbindung an das Netzwerk redundant ausgeführt werden, sodass deren Konnektivität im Fall eines einfachen Fehlers garantiert werden kann. Nachdem diese Art der redundanten Anbindung jedoch häufi g zu teuer ist, erlaubt das bmax-SNDP eine Relaxierung dieser Anforderung. In diesem Fall darf
das letzte Stück des Anschlusses eines C2 Kunden nichtredundant ausgeführt sein.
Diese nichtredundante branch-line darf jedoch eine vorde finierte Länge bmax nicht überschreiten. In dieser Arbeit werden zwei, hinsichtlich der Zielfunktion unterschiedliche,
Varianten des Problems behandelt. Während beim sogenannten \Operative
Planning Task" (OPT) alle gegebenen Kunden möglichst kostengünstig an ein bestehendes Netzwerk angeschlossen werden sollen, wird beim \Strategic Simulation Task" (SST) eine möglichst pro table Lösung gesucht, in welcher eventuell nur eine Teilmenge aller Kunden versorgt wird.
Zur Lösung des Problems werden zwei auf gemischt-ganzzahliger linearer Programmierung beruhende Modelle vorgeschlagen. Diese können mittels Branch-and-Price gelöst werden und liefern beweisbar optimale Lösungen für kleine und mittelgroße Probleminstanzen. Eine Spezialität hierbei ist die Verwendung von alternativen
dualen Lösungen im sogenannten Pricing Problem, wodurch die Lösung der linearen Relaxierung beider Modelle mittels Spaltengenerierung enorm beschleunigt wird. Weiters werden ein hybrider Optimierungsansatz, welcher auf Lagranger Relaxierung
beruht, sowie metaheuristische Methoden zur näherungsweisen Lösung von
sehr großen Instanzen von bmax-SNDP vorgeschlagen. Die erzielten Testergebnisse belegen die E ffektivität der vorgestellten Lösungsansätze.
Speziell in ländlichen Gebieten sind Fiber-to-the-home Netzwerke häufig nicht profitabel.
In solchen Fällen wird oft eine Fiber-to-the-curb Strategie verfolgt. Hier wird das neue Netz nicht bis zum Kunden, sondern nur bis zu Übergabepunkten errichtet.
Sind diese Übergabepunkte (facilities) nahe genug an den jeweils zugewiesenen
Kunden, kann dennoch eine beträchtliche Steigerung der verfügbaren Bandbreite erzielt werden. Derartige Szenarien können als Varianten des Connected Facility
Location Problems (ConFL), bei dem eine Menge an Facilities ausgewählt
und miteinander verbunden werden sollen, modelliert werden. Zusätzlich müssen die Kunden noch diesen Facilities zugeordnet werden. Der zweite Teil dieser Arbeit
beschäftigt sich mit dem Capacitated Connected Facility Location Problem
(CConFL), welches ConFL um wichtige Nebenbedingungen erweitert. Dazu zählen etwa Kapazitätsbeschränkungen für Facilities aufgrund individueller Bandbreitenanforderungen
von Kunden. Das Ziel der Optimierung ist es eine möglichst pro table
Lösung zu berechnen bei der nicht zwangsweise alle potentiellen Kunden versorgt
werden.
Es werden vier auf gemischt-ganzzahliger linearer Programmierung beruhende Verfahren
vorgestellt mit welchen beweisbar optimale Lösungen für CConFL berechnet
werden können. Diese werden anhand ihrer zugrundeliegenden Polyeder aus theoretischer
Sicht 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.


Electronic version of the publication:
http://publik.tuwien.ac.at/files/PubDat_188779.pdf


Created from the Publication Database of the Vienna University of Technology.