Design and implementation of an interactive optimization system for telephone network planning

The authors describe an interactive optimization system for multiperiod exhaust relief planning in the local loop of a public telephone network. In exhaust relief planning in the local loop one seeks the minimum cost capacity expansion plan that meets projected demand over a given planning horizon. The problem can be modeled as an integer programming problem. However, due to cost structures and varying transmission technologies, the single-period exhaust relief planning problem is NP-complete. The size of the problem precludes the use of general purpose integer programming. Based on the mathematical structure and complexity of the problem, the authors decompose the optimization problem into a single-period dynamic programming problem, and a multiperiod greedy heuristic. A software system surrounds the optimization algorithm and provides interactive planning capabilities, before and after creation of the optimized plan. Important aspects of the system are the model assumptions made to keep the problem tractable, and their effect on the standardization of input data and methodology. The system is in use by several hundred outside plant planners in a major U.S. telephone company. An overview of major elements of the package is given as well as a summary of important implementation issues that arose during the first three years of the on-going project.