Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Improving a Branch-and-Bound Approach for the Degree-Constrained Minimum Spanning Tree Problem with LKH

: Thiessen, M.; Quesada, L.; Brown, K.N.


Hebrard, E.:
Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 17th International Conference, CPAIOR 2020. Proceedings : Vienna, Austria, September 21-24, 2020
Cham: Springer Nature, 2020 (Lecture Notes in Computer Science 12296)
ISBN: 978-3-030-58941-7 (Print)
ISBN: 978-3-030-58942-4 (Online)
International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR) <17, 2020, Online>
Fraunhofer IAIS ()

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.