[Back]

M. Riedler:
"Exact approaches to the network design problem with relays";
Supervisor: I. Ljubic, M. Leitner, M. Ruthmair; Computergraphik und Algorithmen, 2014.

In this thesis we develop exact approaches for solving the Network Design Problem with Relays(NDPR). The NDPR can be motivated as follows. We are given a set K of vertex pairs that need to communicate with each other in an undirected graph G = (V;E). A signal is sent from a source to a target from K but after a distance of dmax the signal deteriorates and we need to install a relay to regenerate it. Alternatively, we may install new edges in an existing graph (that can also be empty) to shorten the distance. Every edge e2E has cost we and a distance de. The cost for installing a relay at vertex i2V is ci. The goal of the NDPR is to find a selection of
edges to install and vertices where relays are to be placed enabling communication between the pairs in K s.t. the sum of relay and edge costs is minimal.

The NDPR arises in the context of network design when distance limits have to be kept due to signal deterioration. To cover longer distances equipment for signal regeneration is required. This equipment is expensive and thus minimization is required. Another area of application is e-mobility. E-cars need to recharge after traveling a certain distance. Recharging stations are expensive and one only wants to build as few as necessary. Previous work on the NDPR mainly focuses on heuristic approaches. In the following we are going to present exact solution approaches based on mixed integer linear programming. We introduce compact models, models with an exponential number of constraints, models with an exponential number of variables and models with an exponential number of variables and
constraints. We divide our models w.r.t. the underlying graph transformation. The first set of our models is based on layered graphs and the second one on communication graphs. We test our models against modified versions of instances from the previous literature. One of our algorithms solves the first set of those instances to optimality and also a large amount of the instances of the second set. Moreover, we present a set of entirely new instances containing
a larger number of commodity pairs. Some of our algorithms solve most of these instances to optimality but some of the new instances turned out to be very challenging.

In dieser Arbeit entwickle ich exakte Lösungsansätze für das Network Design Problem with Relays (NDPR). Das NDPR kann folgendermaßen motiviert werden. Gegeben ist eine Menge K von Knotenpaaren die in einem ungerichteten Graphen G = (V;E)kommunizieren müssen.
Ein Signal wird vom ersten Knoten des Paares zum anderen gesendet. Nachdem eine Distanz von dmax zurück gelegt wurde verschlechtert sich das Signal zu sehr und muss durch Platzieren eines relays aufgefrischt werden. Als Alternative können neue Kanten in ein bestehendes (möglicherweise leeres) Netzwerk eingefügt werden, um die zurückgelegte Distanz zu verkleinern. Jede Kante e2E hat Kosten we und eine Distanz de. Die Kosten um ein relay bei Knoten i2V zu installieren, betragen ci. Das Ziel des NDPR ist es eine Menge von zu installierenden Kanten und relays auszuwählen, die Kommunikation zwischen allen Paaren in K ermöglichen, sodass die Summe aus relay- und Kantenkosten minimal ist.Das NDPR findet Anwendung im Netzwerkentwurf, wo Distanzbegrenzungen eingehalten werden müssen, um eine zu starke Signalverschlechterung zu vermeiden. Das Zurücklegen größerer Distanzen erfordert Komponenten zur Auffrischung des Signals. Diese Komponenten sind teuer und daher ist Minimierung notwendig. Ein anderes Anwendungsgebiet ist e-mobility. Elektroautos können nur eine bestimmte Distanz zurücklegen, bevor sie wieder aufgeladen werden müssen. Ladestationen sind teuer, deshalb möchte man nur so wenige wie nötig bauen. Die verfügbare Literatur zum NDPR umfasst hauptsächlich heuristische Ansätze. Im Folgenden werde ich exakte Lösungsansätze vorstellen die auf mixed integer linear programming basieren. In dieser Arbeit stelle ich kompakte Modelle, Modelle mit einer exponentiellen Anzahl an Constraints, Modelle mit einer exponentiellen Anzahl an Variablen und Modelle mit einer ex-
ponentiellen Anzahl an Constraints und Variablen vor. Die Modelle werden im Bezug auf die verwendete Transformation des Graphen unterteilt. Die erste Gruppe von Modellen basiert auf
sogenannten "layered graphs" und die zweite auf sogenannten "communication graphs".

Wir testen unsere Modelle mit modifizierten Instanzen aus der Literatur. Ein Algorithmus löst alle Instanzen der ersten Gruppe optimal und einen Großteil der Instanzen der zweiten Gruppe. Darüber hinaus stelle ich neue Instanzen mit einer größeren Anzahl an Knotenpaaren vor. Einige Algorithmen finden für einen großen Teil dieser Instanzen die optimale Lösung aber ein kleiner Teil der Instanzen erwies sich als besonders schwierig.

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