Spanning trees with a constraint on the number of leaves. A new formulation

In this paper we present a new extended model for the problem of finding a minimum cost spanning tree such that the number of leaves is equal to (greater than, less than) k. We show that with these variables we are able to derive stronger linking constraints in a flow based model permitting us, by using projection techniques, to derive a model with enhanced cut constraints. The new variables also permit us to strengthen, in an extended space, strong inequalities that are well known from the literature. We show that the strengthened inequalities imply a set of inequalities of exponential size, as presented previously by Fujie 8]. A new set of inequalities of exponential size are also implied by the new model will also be proposed. We also discuss the new model in the context of a related problem, the max-leaves problem where one wants to find a spanning tree with a maximum number of leaves. Computational results taken from several sets of instances known from the literature indicate that the new model improves previously known gaps for the three constrained versions and that despite the extra number of variables, it leads to best solution times in almost all cases. For the max-leaves problem the new model proves to be competitive with the existent approaches.