Enhanced Model Representations for an Intra-Ring Synchronous Optical Network Design Problem Allowing Demand Splitting

Hanif D. Sherali, J. Cole Smith, Youngho Lee

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

In this paper, we consider a network design problem arising in the context of deploying synchronous optical networks (SONET) using a unidirectional path switched ring architecture, a standard of transmission using optical fiber technology. Given several rings of this type, the problem is to find an assignment of nodes to possibly multiple rings, and to determine what portion of demand traffic between node pairs spanned by each ring should be allocated to that ring. The constraints require that the demand traffic between each node pair should be satisfiable given the ring capacities, and that no more than a specified maximum number of nodes should be assigned to each ring. The objective function is to minimize the total number of node-to-ring assignments, and hence, the capital investment in add-drop multiplexer equipments. We formulate the problem as a mixed-integer programming model, and propose several alternative modeling techniques designed to improve the mathematical representation of this problem. We then develop various classes of valid inequalities for the problem along with suitable separation procedures for tightening the representation of the model, and accordingly, prescribe an algorithmic approach that coordinates tailored routines with a commercial solver (CPLEX). We also propose a heuristic procedure which enhances the solvability of the problem and provides bounds within 5-13% of the optimal solution. Promising computational results are presented that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs.

Original languageEnglish (US)
Pages (from-to)284-298
Number of pages15
JournalINFORMS Journal on Computing
Volume12
Issue number4
DOIs
StatePublished - 2000

Keywords

  • Sonet ring
  • Valid inequalities

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Enhanced Model Representations for an Intra-Ring Synchronous Optical Network Design Problem Allowing Demand Splitting'. Together they form a unique fingerprint.

Cite this