Improving a branch-and-bound approach for the degree-constrained minimum spanning tree problem with LKH

Simple item page
dc.contributor.authorThiessen, Maximilian
dc.contributor.authorQuesada, Luis
dc.contributor.authorBrown, Kenneth N.
dc.contributor.editorEmmanuel Hebrard and Nysret Musliu
dc.contributor.funderScience Foundation Irelanden
dc.contributor.funderIrish Research Councilen
dc.contributor.funderEnterprise Irelanden
dc.contributor.funderStudienstiftung des Deutschen Volkesen
dc.contributor.funderHorizon 2020en
dc.date.accessioned2020-09-28T16:35:32Z
dc.date.available2020-09-28T16:35:32Z
dc.date.issued2020-09-19
dc.date.updated2020-09-25T15:56:42Z
dc.description.abstractThe degree-constrained minimum spanning tree problem, which involves finding a minimum spanning tree of a given graph with upper bounds on the vertex degrees, has found multiple applications in several domains. In this paper, we propose a novel CP approach to tackle this problem where we extend a recent branch-and-bound approach with an adaptation of the LKH local search heuristic to deal with trees instead of tours. Every time a solution is found, it is locally optimised by our new heuristic, thus yielding a tightened cut. Our experimental evaluation shows that this significantly speeds up the branch-and-bound search and hence closes the performance gap to the state-of-the-art bottom-up CP approach.en
dc.description.sponsorshipScience Foundation Ireland; Chist-ERA project Dyposit (16/SP/3804 and 12/RC/2289 P2 Chist-ERA project Dyposit); European Commission and Enterprise Ireland (grant IR 2017 0041/ EU 737422-2 SCOTT); Studienstiftung des Deutschen Volkes (German Academic Scholarship Foundation)en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationThiessen, M., Quesada, L., and Brown, K.N. (2020) 'Improving a Branch-and-Bound Approach for the Degree-Constrained Minimum Spanning Tree Problem with LKH', in: Hebrard E., Musliu N. (eds). Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2020, Lecture Notes in Computer Science, vol 12296, Cham: Springer International Publishing, pp. 447-456. doi: 978-3-030-58942-4en
dc.identifier.doi10.1007/978-3-030-58942-4en
dc.identifier.endpage456en
dc.identifier.isbn978-3-030-58942-4
dc.identifier.issn0302-9743
dc.identifier.journaltitleLecture Notes in Computer Scienceen
dc.identifier.startpage447en
dc.identifier.urihttps://hdl.handle.net/10468/10595
dc.language.isoenen
dc.publisherSpringeren
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Research Centres/12/RC/2289/IE/INSIGHT - Irelands Big Data and Analytics Research Centre/en
dc.relation.projectinfo:eu-repo/grantAgreement/EC/H2020::ECSEL-IA/737422/EU/Secure COnnected Trustable Things/SCOTTen
dc.relation.urihttps://link.springer.com/chapter/10.1007/978-3-030-58942-4_29
dc.rights© Springer Nature Switzerland AG 2020. The final authenticated version is available online at https://doi.org/10.1007/978-3-030-58942-4_29en
dc.subjectDegree-constrained minimum spanning treeen
dc.subjectBranch-and-bounden
dc.subjectLocal searchen
dc.subjectLKHen
dc.titleImproving a branch-and-bound approach for the degree-constrained minimum spanning tree problem with LKHen
dc.typeBook chapteren
dc.typeConference item
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
paper_39.pdf
Size:
867.63 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items