@inbook{59231791570b4df99c4326e6d8b081b4,
title = "Improving a Branch-and-Bound Approach for the Degree-Constrained Minimum Spanning Tree Problem with LKH",
abstract = "The 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.",
keywords = "Branch-and-bound, Degree-constrained minimum spanning tree, LKH, Local search",
author = "Maximilian Thiessen and Luis Quesada and Brown, \{Kenneth N.\}",
note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 17th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, CPAIOR 2020 ; Conference date: 21-09-2020 Through 24-09-2020",
year = "2020",
doi = "10.1007/978-3-030-58942-4\_29",
language = "English",
isbn = "9783030589417",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "447--456",
editor = "Emmanuel Hebrard and Nysret Musliu",
booktitle = "Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 17th International Conference, CPAIOR 2020, Proceedings",
address = "Germany",
}