Experience with a cutting plane algorithm for the capacitated spanning tree problem

A basic problem in telecommunications network design is that of designing a capacitated centralized processing network. Such a network has a central processor that must be linked via a tree topology to several remote terminals that have specified demands. Each subtree off of the root is constrained to have at most a fixed, limited demand, represented by the sum of the demands of the nodes of the subtree. Finding provably optimal solutions to this class of problems has been surprisingly difficult, particularly for certain types of instances and choices of parameters. This paper presents computational results for the problem, based on a cutting plane algorithm. It first focuses on the unit-demand case, known as the capacitated spanning tree problem, for which the paper present computational experience on a range of instances with up to 200 nodes. It then considers the general-demand case and report on branch-and-cut as well as cutting plane computations on a range of instances, including some from the vehicle routing literature.