You are here

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


Maximilian Thiessen, Luis Quesada, Ken Brown

Publication Type: 
Refereed Conference Meeting Proceeding
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.
Conference Name: 
Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Proceedings of the 17th International Conference, CPAIOR 2020
Digital Object Identifer (DOI): 
Publication Date: 
447 - 456
Conference Location: 
National University of Ireland, Cork (UCC)
Open access repository: 
Publication document: