A 2n constraint formulation for the capacitated minimal spanning tree problem

This paper presents 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, it shows that the linear programming relaxation of both formulations produces optimal solutions with the same cost. The paper presents a brief discussion concerning valid inequalities for the CMST which are directly derived from the new formulation. It shows that some of the new inequalities are not dominated by some sets of facet-inducing inequalities for the CMST. The paper derives 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.