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

Thiessen, Maximilian; Quesada, Luis; Brown, Kenneth N.

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

Files

paper_39.pdf(867.63 KB)

Accepted version

Date

2020-09-19

Authors

Thiessen, Maximilian

Quesada, Luis

Brown, Kenneth N.

Publisher

Springer

Published Version

10.1007/978-3-030-58942-4

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

Degree-constrained minimum spanning tree , Branch-and-bound , Local search , LKH

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