A constraint-based parallel local search for the edge-disjoint rooted distance-constrained minimum spanning tree problem
Loading...
Files
Accepted Version
Date
2017-06-16
Authors
Arbelaez, Alejandro
Mehta, Deepak
O’Sullivan, Barry
Quesada, Luis
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature
Published Version
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 seen as instances of the 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 work on the RDCMST has focused on dedicated algorithms and therefore it is difficult to use these algorithms to tackle the ERDCMST. We present a constraint-based parallel local search algorithm for solving the ERDCMST. Traditional ways of extending a sequential algorithm to run in parallel perform either portfolio-based search in parallel or parallel neighbourhood search. Instead, we exploit the semantics of the constraints of the problem to perform multiple moves in parallel by ensuring that they are mutually independent. The ideas presented in this paper are general and can be adapted to other problems as well. 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, Italy, and the UK. Our results show that performing moves in parallel can significantly reduce the elapsed time and improve the quality of the solutions of our local search approach.
Description
Keywords
Local search , Optical networks , Parallelism
Citation
Arbelaez, A., Mehta, D., O’Sullivan, B. and Quesada, L. (2017) 'A constraint-based parallel local search for the edge-disjoint rooted distance-constrained minimum spanning tree problem', Journal of Heuristics, 24, pp. 359-394. https://doi.org/10.1007/s10732-017-9342-0
Link to publisher’s version
Copyright
© 2017, Springer Science+Business Media, LLC. This is a post-peer-review, pre-copyedit version of an article published in Journal of Heuristics. The final authenticated version is available online at: https://doi.org/10.1007/s10732-017-9342-0