A Constraint-based Local Search for Edge Disjoint Rooted Distance-Constrained Minimum Spanning Tree Problem
Publication Type:
Refereed Conference Meeting Proceeding
Abstract:
Many network design problems arising in areas as diverse as VLSI circuit design, QoS routing,
traffic engineering, and computational sustainability require clients to be connected to a facility under path-length constraints
and budget limits.
These problems can be modelled as
Rooted Distance-Constrained Minimum Spanning-Tree Problem (RDCMST),
which is
NP-hard.
An inherent feature of these networks is that they are vulnerable to
a failure. Therefore, it is often important to ensure that all clients are connected
to two or more facilities via edge-disjoint paths.
We call this problem the Edge-disjoint RDCMST (ERDCMST).
Previous works on RDCMST have focused on dedicated algorithms which
are hard to extend with side constraints, and therefore these algorithms cannot be extended for solving ERDCMST.
We present a constraint-based local search algorithm for which we present
two efficient local move operators and an incremental way of maintaining
objective function.
Our local search algorithm can easily be extended and it is able to solve both problems.
The effectiveness of our approach is demonstrated by experimenting with
a set of problem instances taken from real-world passive optical network
deployments in Ireland, the UK, and Italy.
We compare our approach with existing exact and heuristic approaches.
Results show that our approach is superior to both of the latter
in terms of scalability and its anytime behaviour.
Conference Name:
CPAIOR
Digital Object Identifer (DOI):
http://link.springer.com/chapter/10.1007%2F978-3-319-18008-3_3
Publication Date:
18/05/2015
Conference Location:
Spain
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Project Acknowledges:
Open access repository:
No
Publication document: