A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem

In this paper we present a new formulation for the Capacitated Minimal Spanning Tree (CMST) problem. One advantage of the new formulation is that it is more compact (in the number of constraints) than a well-known formulation. Additionally, we show that the linear programming relaxation of both formulations produces optimal solutions with the same cost. We present a brief discussion concerning valid inequalities for the (CMST) which are directly derived from the new formulation. We show that some of the new inequalities are not dominated by some sets of facet-inducing inequalities for the (CMST). We derive some Lagrangian relaxation-based methods from the new formulation and present computational evidence showing that reasonable improvements on the original linear programming bounds can be obtained if these methods are strengthened by the use of cutting planes. The reported computational results indicate that one of the methods presented in this paper dominates, in most of the cases, the previous best methods reported in the literature. The most significant improvements are obtained in the instances with the root in the corner.