The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm

Given an edge weighted undirected graph G and a positive integer d, the Min-Degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree of G, such that each vertex is either a leaf or else has degree at least d in the tree. In this paper, we discuss two formulations for MDMST based on exponentially many undirected and directed subtour breaking constraints and compare the strength of their Linear Programming (LP) bounds with other bounds in the literature. Aiming to overcome the fact that the strongest of the two models, the directed one, is not symmetric with respect to the LP bounds, we also presented a symmetric compact reformulation, devised with the application of an Intersection Reformulation Technique to the directed model. The reformulation proved to be much stronger than the previous models, but evaluating its bounds is very time consuming. Thus, better computational results were obtained by a Branch-and-cut algorithm based on the original directed formulation. With the proposed method, several new optimality certificates and new best upper bounds for MDMST were provided. (C) 2011 Elsevier B.V. All rights reserved.