Article ID: | iaor20022838 |
Country: | United States |
Volume: | 35 |
Issue: | 3 |
Start Page Number: | 223 |
End Page Number: | 232 |
Publication Date: | May 2000 |
Journal: | Networks |
Authors: | Sherali Hanif D., Kim Seong-in, Lee Youngho, Han Junghee |
Keywords: | networks, programming: branch and bound |
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.