AN EFFICIENT ALGORITHM FOR THE MULTIPERIOD CAPACITY EXPANSION OF ONE LOCATION IN TELECOMMUNICATIONS

The minimum cost multiperiod capacity expansion of one location in telecommunications network planning can be formulated as a time-dependent knapsack problem. The problem consists of meeting integral demands at distinct time periods at minimum total discounted cost through a selection of items (with integral costs and capacities) from a collection of N distinct types of objects. This note presents an efficient pseudopolynomial time solution to this time-dependent knapsack problem. The technique involves an initial dynamic programming run with time complexity O(N(D + C)) followed by a shortest path algorithm with worst-case time complexity O((CT)-T-2) through a suitably defined network, where D and C are the maxima of the values of the demands and capacities, and T is the number of time periods to be considered. The application of this technique to the problem of optimal capacity expansion of one location in telecommunications network planning is described and computational results are reported.