A constraint-based local search for Edge Disjoint Rooted Distance-Constrained Minimum Spanning Tree Problem
| dc.contributor.author | Arbelaez, Alejandro | en |
| dc.contributor.author | Mehta, Deepak | en |
| dc.contributor.author | O’Sullivan, Barry | en |
| dc.contributor.author | Quesada, Luis | en |
| dc.contributor.editor | Michel, Laurent | en |
| dc.contributor.funder | Science Foundation Ireland | en |
| dc.contributor.funder | Seventh Framework Programme | en |
| dc.date.accessioned | 2024-01-24T11:19:01Z | |
| dc.date.available | 2024-01-24T11:19:01Z | |
| dc.date.issued | 2015-01-01 | en |
| dc.description.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. | en |
| dc.description.sponsorship | Science Foundation Ireland (10/CE/I1853) | en |
| dc.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.citation | Arbelaez, A., Mehta, D., O’Sullivan, B. and Quesada, L. (2015) 'A constraint-based local search for Edge Disjoint Rooted Distance-Constrained Minimum Spanning Tree Problem', in: Michel, L. (ed) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015, pp 31-46. Lecture Notes in Computer Science, 9075. Springer, Cham. https://doi.org/10.1007/978-3-319-18008-3_3 | en |
| dc.identifier.doi | 10.1007/978-3-319-18008-3_3 | en |
| dc.identifier.endpage | 46 | en |
| dc.identifier.isbn | 9783319180076 | en |
| dc.identifier.isbn | 9783319180083 | en |
| dc.identifier.issn | 0302-9743 | en |
| dc.identifier.issn | 1611-3349 | en |
| dc.identifier.startpage | 31 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/15429 | |
| dc.language.iso | en | en |
| dc.publisher | Springer Nature Ltd. | en |
| dc.relation.ispartof | Integration of AI and OR Techniques in Constraint Programming | en |
| dc.relation.ispartof | Lecture Notes in Computer Science | en |
| dc.relation.ispartofseries | Lecture Notes in Computer Science; 9075 | en |
| dc.relation.project | info:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/ | en |
| dc.relation.project | info:eu-repo/grantAgreement/EC/FP7::SP1::ICT/318137/EU/The DIStributed Core for unlimited bandwidth supply for all Users and Services/DISCUS | en |
| dc.rights | © 2015, Springer International Publishing Switzerland. This version of the paper has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/978-3-319-18008-3_3 | en |
| dc.subject | Local search | en |
| dc.subject | Span tree | en |
| dc.subject | Local search algorithm | en |
| dc.subject | Network design problem | en |
| dc.subject | Move operator | en |
| dc.title | A constraint-based local search for Edge Disjoint Rooted Distance-Constrained Minimum Spanning Tree Problem | en |
| dc.type | Conference item | en |
