The Capacitated Minimal Spanning Tree Problem: An experiment with a hop-indexed model

The Capacitated Minimal Spanning Tree Problem (CMSTP) is to find a minimal spanning tree with an additional cardinality constraint on the size of the subtrees off of a given root node. This problem is closely related to the design of centralized networks where one wants to link, with minimum cost, several terminals to a given root node (typically, a concentrator or a computer center). In this paper, we present a new extended and compact formulation for the CMSTP. This formulation is a "hop-indexed" single-commodity flow model and generalizes a well-known single-commodity flow model. We introduce a new set of valid inequalities, denoted by "hop ordering" inequalities, which are not redundant for the LP relaxation of the new formulation. We present a new cutting plane method for the CMSTP with the new formulation as the initial model and using constraint generation for adding "hop-ordering" constraints and generalized subtour elimination constraints to the current LP model. We present computational results from a set of tests with 40 and 80 nodes which compare our lower bounds with the bounds given by other known methods. The main contribution of our proposed method is to considerably close previously known gaps for tests which have been classified as hard ones, namely tightly capacitated tests with the root in the corner of the grid of points.