[Zurück]

R. Karl:
"The rooted delay-constrained steiner tree problem with uncertain delays";
Betreuer/in(nen): G. Raidl, M. Leitner, M. Ruthmair; Institut für Computergraphik and Algorithmen, 2013; Abschlussprüfung: 12/2013.

Das Rooted Delay-Constrained Steiner Tree (RDCST) Problem ist ein kombinatorisches Optimierungsproblem,
bei dem ein Baum in einem gegebenen gewichteten Graphen gesucht wird.
Dieser Baum soll ein minimales Gesamtgewicht haben, welches als die Summe der Kantengewichte
definiert ist. Für den Baum gelten dabei zwei Nebenbedingungen. Die erste legt fest, dass
die sogenannten Terminal-Knoten im Baum enthalten sein müssen. Zusätzlich zu den Gewichten
werden für alle Kanten auch Übertragungszeiten definiert. Die zweite Nebenbedingung ist,
dass die Gesamtübertragungszeit auf jedem Pfad zwischen dem gegebenen Wurzelknoten und
einem Terminal-Knoten unter einer bestimmten Schranke liegen muss. Das Problem findet eine
Anwendung bei der Planung von Netzwerken. Für viele Dienste ist es besonders wichtig, dass
die Übertragungszeiten zwischen Client und Server nicht zu hoch werden. Typisch hierfür sind
Netzwerk-Anwendungen mit Benutzer-Interaktion.
Bei Optimierungsalgorithmen geht man oft davon aus, dass alle Eingabewerte genau bestimmt
werden können. In der Praxis kommt es allerdings häufig vor, dass diese Werte einer
gewissen Unsicherheit unterliegen. Ungenauigkeiten entstehen zwangsläufig bei vielen Messungen.
Andere Quellen für Unsicherheiten sind Daten, die erst in der Zukunft entstehen und
davor nur geschätzt werden können. Lösungen von klassischen Optimierungsproblemen können
durch die Schwankungsbreite der zugrunde liegenden Daten ungültig und aus diesem Grund
in der Praxis mitunter gar nicht mehr verwendet werden. Auch die Übertragungszeiten in einem
Netzwerk unterliegen häufig einer merkbaren Schwankung. Wir untersuchen anhand des
RDCST Problems, welche Möglichkeiten zur Verfügung stehen, um Unsicherheiten in den Optimierungsprozess
einzubeziehen.
Wir stellen Algorithmen basierend auf ganzzahliger linearer Programmierung vor, mit denen
es möglich ist, Lösungen zu realistischen Instanzen des Optimierungsproblems zu finden. Diese
Lösungen weisen eine gewissen Grad an Robustheit auf, was bedeutet, dass sie auch bei einer
Schwankung derWerte gültig bleiben. Dieser Grad kann aufgrund der jeweiligen Anforderungen
an die Lösungen variiert werden. Die behandelten Algorithmen sind exakt, finden also die beste
Lösung, die alle Bedingungen erfüllt. Wir stellen einige Alternativen vor, wie die Unsicherheiten
in die Definition des RDCST Problems und in die entsprechenden Algorithmen eingebunden
werden können. Sowohl für das deterministische Problem als auch für allgemeine robuste Probleme
stehen bereits Lösungsansätze im Bereich der ganzzahligen linearen Programmierung zur
Verfügung. Wir zeigen, wie beide Ansätze kombiniert werden können.

The rooted delay-constrained Steiner tree (RDCST) problem is a combinatorial optimization
problem. The task is to find a tree in a given weighted graph. The tree should have minimal
weight which is defined as the sum of the edge weights. Furthermore, it should satisfy two
constraints. The first is that the so-called terminal nodes have to be part of the tree. Additionally
to the weight, every edge has also a given delay. The second constraint is that the overall delay
on a path from a given root node to a terminal node stays within a given bound. This problem
sometimes occurs when planning networks. For many services it is important that the delay
between client and server does not get too high. A typical example are network applications
with user interaction.
In optimization algorithms we usually assume that all input values are given precisely. But
in practice these values are often affected by some kind of uncertainty. Inaccuracies occur inevitably
with many measurements. Another source for uncertainty is data that is not yet present
and therefore has to be predicted. Solutions of optimization problems can become infeasible
because of the variability of input data. In practice this often means that the solution is of no
use. Also the delays in a network are commonly affected by some jitter. We investigate for the
RDCST problem how uncertainties can be incorporated into the optimization process.
We present algorithms based on mixed integer linear programming with which it is possible
to find solutions of realistic instances of the optimization problem. These solutions feature a
specific degree of robustness, which means that they stay feasible if actual values diverge from
the assumed values. This degree can be adjusted accordingly to the respective requirements. The
examined algorithms are exact. Thus, the best solution is found which fulfils the constraints. We
present several ways of including uncertainties into the definition of the RDCST problem and its
solution algorithms.
There are already methods to solve both the deterministic problem and general robust problems
with integer linear programs. We show how both methods can be combined.

http://publik.tuwien.ac.at/files/PubDat_224700.pdf