A branch-and-cut algorithm for solving an intraring synchronous optical network design problem

A branch-and-cut algorithm for solving an intraring synchronous optical network design problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: networks, programming: branch and bound
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.