Combined network design and multiperiod pricing: Modeling, solution techniques, and computation
成果类型：
Article
署名作者：
Bienstock, D; Raskina, O; Saniee, I; Wang, Q
署名单位：
Columbia University; AT&T
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1050.0259
发表日期：
2006
页码：
261-276
关键词：
摘要：
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 all 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.