Combined Network Design and Multiperiod Pricing: Modeling, Solution Techniques, and Computation

In this paper we describe an efficient algorithm for solving novel optimization models arising in the context of multiperiod capacity expansion of optical networks. We assume that the network operator must make investment decisions over a multiperiod planning horizon while facing rapid changes in transmission technology, as evidenced by a steadily decreasing per-unit cost of capacity. We deviate from traditional and monopolistic models in which demands are given as input parameters, and the objective is to minimize capacity deployment costs. Instead, we assume that the carrier sets end-to-end prices of bandwidth at each period of the planning horizon. These prices determine the demands that are to be met, using a plausible and explicit price-demand relationship; the resulting demands must then be routed, requiring an investment in capacity. The objective of the optimization is now to simultaneously select end-to-end prices of bandwidth and network capacities at each period of the planning horizon, so as to maximize the overall net present value of expanding and operating the network. In the case of typical large-scale optical networks with protection requirements, the resulting optimization problems pose significant challenges to standard optimization techniques. The complexity of the model, its nonlinear nature, and the large size of realistic problem instances motivates the development of efficient and scalable solution techniques. We show that while general-purpose nonlinear solvers are typically not adequate for the task, a specialized decomposition scheme is able to handle large-scale instances of this problem in reasonable time, producing solutions whose net present value is within a small tolerance of the optimum.