Citation:Thiessen, 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-4
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.
This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement