An efficient branch and bound algorithm for CMST problem

To resolve a fundamental and significant problem in the optimal design of communication networks-the capacitated minimum spanning tree (CMST) problem, with flow volume constraints-we propose a hybrid optimization method in combination with the branch and bound technique and the heuristic search method. By using the neighborhood searching strategy, the initial solution was substantially improved. The proposed algorithm raises the efficiency of ergodic search trees and speeds up pruning. The results were verified with several experiments. The advantages of this algorithm in searching for the optimal solution were demonstrated, showing that the proposed algorithm is more efficient than the previous arc-orientated branch and bound algorithm.