Premium
A branch‐and‐cut algorithm for solving an intraring synchronous optical network design problem
Author(s) -
Lee Youngho,
Sherali Hanif D.,
Han Junghee,
Kim Seongin
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(200005)35:3<223::aid-net6>3.0.co;2-j
Subject(s) - synchronous optical networking , branch and cut , computer science , integer programming , multiplexer , node (physics) , graph partition , ring network , cardinality (data modeling) , algorithm , network planning and design , mathematical optimization , graph , theoretical computer science , mathematics , network topology , multiplexing , computer network , structural engineering , engineering , data mining , telecommunications
In this paper, we deal with a network design problem arising from the deployment of synchronous optical networks (SONET), a standard of transmission using optical fiber technology. The problem is to find an optimal clustering of traffic demands in the network such that the total number of node assignments (and, hence, add—drop multiplexer equipment requirements) is minimized, while satisfying the ring capacity and node cardinality constraints. This problem can be conceptualized as an edge‐capacitated graph partitioning problem with node cardinality constraints. We formulate the problem as a mixed‐integer programming model and develop a new branch‐and‐cut algorithm along with preprocessing routines for optimally solving the problem. We also prescribe an effective heuristic procedure. Promising computational results are obtained using the proposed method. © 2000 John Wiley & Sons, Inc.