Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem

We develop ideas to enhance the performance of the variable neighborhood search (VNS) by guiding the search in the shaking phase, and by employing the Skewed strategy. For this purpose, Second Order algorithms and Skewed functions expressing structural differences are embedded in an efficient VNS proposed in the literature for the degree constrained minimum spanning tree problem. Given an undirected graph with weights associated with its edges, the degree constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. Computational experiments are conducted on the largest and hardest benchmark instances found in the literature to date. We report results showing that the VNS with the proposed strategies improved the best known solutions for all the hardest benchmark instances. Moreover, these new best solutions significantly reduced the gaps with respect to tight lower bounds reported in the literature.