A stochastic intra-ring synchronous optimal network design problem

Abstract

We develop a stochastic programming approach to solving an intra-ring Synchronous Optical Network (SONET) design problem. This research differs from pioneering SONET design studies in two fundamental ways. First, while traditional approaches to solving this problem assume that all data are deterministic, we observe that for practical planning situations, network demand levels are stochastic. Second, while most models disallow demand shortages and focus only on the minimization of capital Add-Drop Multiplexer (ADM) equipment expenditure, our model minimizes a mix of ADM installations and expected penalties arising from the failure to satisfy some or all of the actual telecommunication demand. We propose an L-shaped algorithm to solve this design problem, and demonstrate how a nonlinear reformulation of the problem may improve the strength of the generated optimality cuts. We next enhance the ba-sic algorithm by implementing powerful lower and upper bounding techniques via an assortment of modeling, valid inequality, and heuristic strategies. Our computational results conclusively demonstrate the efficacy of our proposed algorithm as opposed to standard L-shaped and extensive form approaches to solving the problem.