An Improved Node Partitioning Algorithm for the CMST Problem

Abstract—The capacitated minimum spanning tree (CMST) problem is one of the most fundamental and significant problems in the optimal design of communication networks. In this paper several methods are proposed to improve existing node-oriented branch and bound algorithm for the CMST problem. Techniques for acquiring tighter lower bound are emphasized, while regulations for faster traversing of the search tree are proposed on the basis of comprehensive observation of the search procedure. Computational experiences demonstrate that the proposed methods significantly improved the efficiency of the existing algorithms. Moreover, as an exact algorithm, the proposed one is the first algorithm that solved the 41 node te-class benchmark problem instances. Keywords-Branch and bound; Search tree; Pruning; Penalty I