The rooted delay-constrained Steiner tree problem with uncertain delays

Abstract

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 der Werte 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 fulfills 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.