A stochastic integer programming approach to solving a synchronous optical network ring design problem

J. Cole Smith, Andrew J. Schaefer, Joyce W. Yen

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

We develop stochastic integer programming techniques tailored toward solving a Synchronous Optical Network (SONET) ring design problem with uncertain demands. Our approach is based on an L-shaped algorithm, whose (integer) master program prescribes a candidate network design, and whose (continuous) subproblems relay information regarding potential shortage penalty costs to the ring design decisions. This naive implementation performs very poorly due to two major problems: (1) the weakness of the master problem relaxations, and (2) the limited information passed to the master problem by the optimality cuts. Accordingly, we enforce certain necessary conditions regarding shortage penalty contributions to the objective function within the master problem, along with a corresponding set of valid inequalities that improves the solvability of the master problem. We also show how a nonlinear reformulation of the model can be used to capture an exponential number of optimality cuts generated by the linear model. We augment these techniques with a powerful upper-bounding heuristic to further accelerate the convergence of the algorithm, and demonstrate the effectiveness of our methodologies on a test bed of randomly generated stochastic SONET instances.

Original languageEnglish (US)
Pages (from-to)12-26
Number of pages15
JournalNetworks
Volume44
Issue number1
DOIs
StatePublished - Aug 2004
Externally publishedYes

Keywords

  • Decomposition
  • L-shaped method
  • Network design
  • SONET
  • Stochastic integer programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'A stochastic integer programming approach to solving a synchronous optical network ring design problem'. Together they form a unique fingerprint.

Cite this