A BRANCH-AND-BOUND ALGORITHM FOR THE CAPACITATED MINIMUM SPANNING TREE PROBLEM

Given an undirected graph G = (N, E) with a cost associated with each edge C: E --> R, and a demand associated with each node A: N --> R+. A special node is designated as the center. The capacitated minimum spa nning tree (CMST) problem is to find a minimum spanning tree for graph G such that the sum of demands on each branch stem from the center do es not exceed a given capacity. The CMST problem has many applications in network design, centralized telecommunications, and vehicle routin g. In this paper, we present a new formulation and a full optimization algorithm by branch and bound. The lower bounds are generated by Lagr angean relaxation with tightening constraints. Computational results b ased upon the methodology presented are shown. (C) 1993 by John Wiley & Sons, Inc.