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 procesor 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. We first focus on the unit-demand case, known as the capacitated spanning tree problem, for which we present computational experience on a range of instances with up to 200 nodes. We then consider 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.