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
In @cite_4 the SRAP problem is considered. They propose three greedy algorithms with different heuristics, the , the and the . The first two algorithms start by assigning each node to a different ring. At each iteration they reduce the number of rings by merging two rings @math and @math if @math is a feasible ring for the capacity constraint. In the edge-based heuristic, the two rings with the maximum weight edge are merged. While in the cut-based heuristic, the two rings with the maximum total weight of the edges with one endpoint in each of them, are merged. Algorithm shows the pseudo code for the edge-based heuristic.
@cite_4
2002547394
We consider the problem of interconnecting a set of customer sites using bidirectional SONET rings of equal capacity. Each site is assigned to exactly one ring and a special ring, called the federal ring, interconnects the other rings together. The objective is to minimize the total cost of the network subject to a ring capacity limit where the capacity of a ring is determined by the total bandwidth required between sites assigned to the same ring plus the total bandwidth request between these sites and sites assigned to other rings.We present exact, integer-programming based solution techniques and fast heuristic algorithms for this problem. We compare the results from applying the heuristic algorithms with those produced by the exact methods for real-world as well as randomly generated problem instances. We show that two of the heuristics find solutions that cost at most twice that of an optimal solution. Empirical evidence indicates that in practice the algorithms perform much better than their theoretical bound and often find optimal solutions.