This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Bienstock, D. Articles by Wang, Q. Search for Related Content

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

Department of Industrial Engineering and Operations Research, Columbia University, 500 W. 120th Street, New York, New York 10027
Emptoris, Incorporated, 200 Wheeler Road, Burlington, Massachusetts 01803
Bell Laboratories, 600 Mountain Avenue, Murray Hill, New Jersey 07974
Bell Laboratories, 600 Mountain Avenue, Murray Hill, New Jersey 07974
dano{at}columbia.edu
oraskina{at}emptoris.com
iis{at}research.bell-labs.com
qwang{at}research.bell-labs.com

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.

Subject classifications: communications; facility/equipment planning; capacity expansion; design; maintenance/replacement; programming; nonlinear.
History: Received May 2003; revision received December 2003; accepted January 2005.

This article has been cited by other articles:

				L. Brotcorne, M. Labbe, P. Marcotte, and G. Savard Joint Design and Pricing on a Network Operations Research, September 1, 2008; 56(5): 1104 - 1115. [Abstract] [PDF]