The capacitated minimum spanning tree problem: revisiting hop-indexed formulations

摘要

The capacitated minimum spanning tree problem is to find a minimum spanning tree with an additional cardinality constraint on the number of nodes in any subtree off a given root node. In this paper we propose two improvements on a previous cutting-plane method proposed by Gouveia and Martins (Networks 35(1) (2000) 1) namely, a new set of inequalities that can be seen as hop-indexed generalization of the well known generalized subtour elimination (GSE) constraints and an improved separation heuristic for the original set of GSE constraints. Computational results show that the inclusion of the new separation routine and the inclusion of the new inequalities in Gouveia and Martins' iterative method (see (Networks 35(1) (2000) 1)) produce improvements on previously reported lower bounds. Furthermore, with the improved method, several of previous unsolved instances have been solved to optimality.