HEURISTIC BRANCH-AND-BOUND ALGORITHM FOR TELEPHONE FEEDER CAPACITY EXPANSION

An adaptation is presented of a branch-and-bound solution approach for the problem of expanding the capacity of a telephone feeder cable network to meet growing demand. This search has been trimmed by generating ″heuristic″ bounds, based on ″analytic″ solutions of simpler capacity expansion problems. Although the guarantee of exact optimality is sacrificed, very good results are obtained 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. It is believed 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.