VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

Given an undirected graph with weights associated with its edges, the min-degree constrained minimum spanning tree (mdmd-MST) problem consists in finding a minimum spanning tree of the given graph, imposing minimum degree constraints in all nodes except the leaves. This problem was recently proposed in Almeida et al. [Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, Working-paper no. 6; 2006], where its theoretical complexity was characterized and showed to be NPNP-hard.The present paper discusses variable neighborhood search (VNS) metaheuristics addressing the mdmd-MST. A so-called enhanced version of a second order (ESO) repetitive technique is also considered, in order to guide the search in both shaking and improvement phases of the VNS method. A Kruskal based greedy heuristic adapted to the mdmd-MST is also presented, being used within the ESO framework. VNS randomized methodologies are also discussed. These are the first heuristics to the mdmd-MST ever proposed in the literature. Computational experiments are conducted on instances adapted from benchmark ones used in the context of the well-known degree constraint minimum spanning tree problem. These experiments have shown that randomized VNS methods enclosing an ESO algorithm can produce very interesting results. In particular, that a simpler VNS randomized methodology might be taken into account when very high dimensional instances are under consideration.