M. Ruthmair, A. Hubmer, G. Raidl:

"Using a Solution Archive to Enhance Metaheuristics for the Rooted Delay-Constrained Minimum Spanning Tree Problem";

Talk: International Conference on Computer Aided Systems Theory (Eurocast), Gran Canaria, Spain; 2011-02-06 - 2011-02-11; in: "Extended Abstracts of EUROCAST 2011 - 13th International Conference on Computer Aided Systems Theory", (2011), ISBN: 978-84-693-9560-8; 285 - 287.

When designing a communication network with a central server broadcasting

information to all the participants of the network, some applications, such as

video conferences, require a limitation of the maximal delay from the server to

each client. Beside this delay-constraint minimizing the cost of establishing the

network is in most cases an important design criterion. This network design

problem can be modeled as an NP-hard combinatorial optimization problem

called rooted delay-constrained minimum spanning tree (RDCMST) problem. The

objective is to find a minimum cost spanning tree of a given graph with the

additional constraint that the sum of delays along the paths from a specified

root node to any other node must not exceed a given delay-bound.

More formally, we are given an undirected graph G = (V;E) with a set V

of n nodes, a set E of m edges, a cost function c : E ! R+

0 , a delay function

d : E ! R+, a fixed root node s 2 V , and a delay-bound B > 0. An optimal

solution to the RDCMST problem is a spanning tree T = (V;E0); E0 E, with

minimum cost c(T) =

Σ

e2E0 c(e), satisfying the constraints

Σ

e2P(s;v) d(e)

B; 8v 2 V , where P(s; v) denotes the unique path from root s to node v.

Exact approaches to the RDCMST problem have been examined by Gouveia

et al. in [1] based on the concept of constrained shortest paths utilized in column

generation, Lagrangian relaxation methods and a flow-based reformulation of the

problem on layered acyclic graphs. All these methods can only solve small instances

with significantly less than 100 nodes to proven optimality in reasonable

time when considering complete graphs. A constructive heuristic approach based

on Primīs algorithm to find a minimum spanning tree is described by Salama

et al. in [6]. In [4] we present a more de-centralized approach by applying the

basic concept of Kruskalīs minimum spanning tree algorithm to the RDCMST

problem. Two metaheuristics based on GRASP and variable neighborhood descent

(VND) improve the constructed solution. In [5] we reuse this VND as the

local search component in a general variable neighborhood search (GVNS) and

a MAX MIN ant system (MMAS). The MMAS mostly obtains the best

results in the performed tests.

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

Created from the Publication Database of the Vienna University of Technology.