Regenerator Location Problem

Intro

In optical networks, the strength of an optical signal deteriorates as it gets farther from the source due to transmission impairments in the fiber (attenuation, dispersion, cross-talk). In other words, the distance an optical signal may be sent without losing or falsifying the information is limited. Therefore, it is necessary to regenerate the signals periodically using regenerators. Given an optical network, the regenerator location problem searches for the subset of regenerators to be installed at minimum cost, so that each pair of nodes can communicate with each other.

Definition

Mathematically, the regenerator location problem (RLP) can be described as follows. We are given:

a network G = {N,F,D} where N is the set of nodes, F is the set of edges, and D is the associated distance matrix of edges,
a maximum distance of dmax that determines how far a signal can traverse before its quality deteriorates and needs to be regenerated, and
a non-negative cost w(i) for installing regenerator at node i, for each i in N.

The goal is to determine a subset of nodes L of minimum cost, such that for every pair of nodes in N there exists a path in G with the property that there is no subpath (i.e., a subsequence of edges on the path) with length > dmax without internal regenerators.

Complexity

The problem is NP-complete (see [1]).
In case of uniform regenerator costs, the RLP is equivalent to the Maximum Leaf Spanning Tree Problem (MLSTP) (aka the Minimum Connected Dominating Set problem).

Input graph G after preprocessing
(two nodes are connected iff the length of the
shortest path ≤dmax)

A feasible RLP solution

Corresponding MLSTP solution

Benchmark Instances

Here you can download instances that have been used in our paper:
The regenerator location problem, Networks 55(3): 205-220, 2010, by S. Chen, I. Ljubić, and S. Raghavan.
This is one of the two most cited Networks paper in 2010.
Three groups of instances are available:
- randomly generated instances (40-100 nodes)
- weighted instances (40-100 nodes)
- larger randomly generated instances (200-500 nodes)

Data Format

Graphs are provided after preprocessing, i.e., we proceed with the distance matrix D as follows: a node pair (u,v) is connected by an edge iff the length of the shortest path between u and v is ≤dmax. The nodes that are not connected by an edge are called not directly connected or NDC node pairs.

Each instance file starts with "nNodes" which is the number of total nodes and then "nPairs" which is the number of NDC node pairs, followed by a nNodes x nNodes matrix A, denoted by "Cost", and followed by a list of NDC node pairs, denoted by "UnPairedArc". Finally, if instances are weighted, before providing the "Cost" matrix, a list of node weights, denoted by "Weight" is given.
a(u,v)=0 in the matrix "Cost" indicates that there is a direct connection between nodes u and v.

Binliography

S. Chen, I. Ljubić, and S. Raghavan: The regenerator location problem, Networks 55(3): 205-220, 2010

Ivana LJUBIC