This paper presents a new method and a constraint-based objective function to solve two problemsrelated to the design of optical telecommunication networks, namely the Synchronous Optical Net-work Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network DesignProblem (IDP). These network topology problems can be represented as a graph partitioning withcapacity constraints as shown in previous works. We present here a new objective function and anew local search algorithm to solve these problems. Experiments conducted in C
Y. Lee, H. Sherali, J. Han and S. Kim in 2000 ( @cite_7 ), have studied the IDP problem with an additional constraint such that for each ring @math , @math . The authors present a mixed-integer programming model for the problem, and develop a branch-and-cut algorithm. They also introduce a heuristic to generate an initial feasible solution, and another one to improve the initial solution. To initialize a ring, the heuristic first, adds the node @math with the maximum graph degree, with respect to unassigned edges, and then adds to the partition the edge @math such that the graph degree of @math is maximum. It iteratively increases the partition by choosing a node such that the total traffic does not exceed the limit @math . A set of 40 instances is generated to test these heuristics and the branch-and-cut.
@cite_7
2101186575
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.