[Zurück]


Diplom- und Master-Arbeiten (eigene und betreute):

M. Sinnl:
"Branch-and-price for the Steiner tree problem with revenues, budget and hop constraints";
Betreuer/in(nen): G. Raidl, M. Leitner; Institut für Computergraphik und Algorithmen, 2011; Abschlussprüfung: 08/2011.



Kurzfassung deutsch:
Diese Diplomarbeit behandelt das Steiner tree problem with revenues, budget and hop constraints
(STPRBH), ein NP-schweres kombinatorisches Optimierungsproblem mit Anwendungen
unter anderem im Design von Telekommunikationsnetzen. Eine Instanz des STPRBH besteht
aus einem ungerichteten Graphen mit einem Wurzelknoten, Knoten, die nicht-negativen
Ertrag generieren, falls sie in einer Lösung mit dem Wurzelknoten verbunden sind und Kanten
mit positivem Gewicht.Weiters ist ein Budget B 0 und ein HoplimitH 2 N Teil einer Instanz.
Erlaubte Lösungen sind alle Steiner-Bäume dieses Graphen, die denWurzelknoten enthalten und
in denen jeder Pfad vom Wurzelknoten bis zu einem anderen Knoten im Baum höchstens aus
H Kanten besteht. Weiters darf die Summe der Gewichte der Kanten im Baum höchstens B
betragen. Ziel ist es, eine gültige Lösung mit möglichst hohem Gewinn, der durch die Summe
der Erträge der in der Lösung vorhandenen Knoten definiert ist, zu finden.
Es werden mehrere Formulierungen für das STPRBH als ganzzahliges lineares Programm
(ILP) mit exponentiell vielen Variablen vorgeschlagen. Außerdem werden branch-and-price
Verfahren, die auf diesen Formulierungen basieren und das exakte Lösen von Instanzen des
STPRBH erlauben, eingeführt. Bei der Anwendung dieser branch-and-price Ansätze in der Praxis
treten aber verschiedenste Probleme auf. Deshalb wird die Anwendbarkeit verschiedener
Möglichkeiten deren Effizienz zu verbessern analysiert. Diese Möglichkeiten umfassen Stabilisierungstechniken,
verschiedene Pricing-Strategien und Heuristiken, um Startlösungen zu generieren.
Tests auf schon existierenden Benchmark-Instanzen zeigen, dass die vorgeschlagenen
branch-and-price Ansätze kompetitiv mit schon existierenden exakten Verfahren, die auf branchand-
price basieren, sind, falls das Hoplimit oder die Anzahl der Knoten mit positivem Ertrag
vergleichsweise klein ist. In Instanzen, in denen das Budget B keine Rolle spielt (d.h. hoch genug
ist, um keine Einschränkung darzustellen), sind die branch-and-price Verfahren sogar meist
klar besser als die branch-and-cut Verfahren. Es muss aber beachtet werden, dass diese spezifische
Variante des STPRBH nicht NP-schwer ist. Für Instanzen mit großem Hoplimit oder einer
großen Anzahl von Knoten mit positivem Ertrag sind die vorgeschlagenen branch-and-price
Verfahren noch nicht kompetitiv mit den branch-and-cut Verfahren. Durch die implementierten
Stabilisierungsmethoden und Beschleunigungsmethoden wurde aber eine signifikante Beschleunigung
der branch-and-price Verfahren erreicht.

Kurzfassung englisch:
This thesis deals with the Steiner tree problem with revenues, budget and hop constraints
(STPRBH), an NP-hard combinatorial optimization problem with applications in telecommunications
network design. An instance of the STPRBH is defined by a connected graph with a
dedicated root node, a set of nodes with nonnegative revenues and positive costs assigned to edges.
Furthermore, a budget B 0 and a hop limit H 2 N are given. The set of feasible solutions
is given by all Steiner trees containing the root node, where every path from the root node to
any other node in the tree contains at most H edges. Furthermore, the total edge costs of such
a tree must be lower or equal to the given budget B. The goal is to find a feasible solution with
maximum revenue, i.e. to maximize the sum of revenues associated with nodes which are part
of the solution.
Several formulations for the STPRBH based on integer linear programming using exponentially
many variables are presented. Furthermore, branch-and-price approaches based on these
formulations are introduced that allow for solving instances of the STPRBH to proven optimality.
The practical implementations of these branch-and-price approaches do, however, suffer
from various problems. Thus, the applicability of various attempts to improve their efficiency
like stabilization techniques, different pricing strategies and heuristic methods to generate initial
solutions is analyzed. Furthermore, promising methods are correspondingly adapted and applied
to the STPRBH.
Tests on previously existing benchmark instances show that the presented branch-and-price
approaches are competitive with existing exact methods based on branch-and-cut when the hop
limit is rather restrictive or if the number of nodes with positive revenue is relatively small.
Furthermore, when the budget B does not play a role (i.e. is high enough to pose no restriction),
branch-and-price usually outperforms branch-and-cut. It should be noted, however, that this
specific variant of the STPRBH is not NP-hard. For instances with a large hop limit or a large
number of nodes with positive revenue the proposed branch-and-price approaches are not yet
competitive to branch-and-cut. Due to the implemented stabilization and acceleration methods a
significant speed-up of branch-and-price has, however, been achieved for these instances too.


Elektronische Version der Publikation:
http://publik.tuwien.ac.at/files/PubDat_200753.pdf


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.