A Heuristic Branch-and-Bound Algorithm for Telephone Feeder Capacity Expansion

We present an adaptation of a branch-and-bound solution approach for the problem of expanding the capacity of a telephone feeder cable network to meet growing demand. We drastically trim the search by generating “heuristic” bounds, based on “analytic” solutions of simpler capacity expansion problems. Although we have thus sacrificed a guarantee of exact optimality, we obtain very good solutions with far less computation than would otherwise be possible. Computational efficiency is important because the algorithm is implemented in a computer program that is used routinely, both in “batch” and “time-share” versions, by telephone company planners and engineers. We believe that this approach of using the flexibility of a branch-and-bound formulation, along with specialized heuristics to limit the search, can provide a practical compromise between a “pure” search for an exact optimum and a “no search” use of a heuristic alone