The Minimum Cost Design of Transparent Optical Networks Combining Grooming, Routing, and Wavelength Assignment

As client demands grow, optical network operators are required to introduce lightpaths of higher line rates in order to groom more demand into their network capacity. For a given fiber network and a given set of client demands, the minimum cost network design is the task of assigning routing paths and wavelengths for a minimum cost set of lightpaths able to groom all client demands. The variant of the optical network design problem addressed in this paper considers a transparent optical network, single hop grooming, client demands of a single interface type, and lightpaths of two line rates. We discuss two slightly different mixed integer linear programming models that define the network design problem combining grooming, routing, and wavelength assignment. Then, we propose a parameters increase rule and three types of additional constraints that, when applied to the previous models, make their linear relaxation solutions closer to the integer solutions. Finally, we use the resulting models to derive a hybrid heuristic method, which combines a relax-and-fix approach with an integer linear programming-based local search approach. We present the computational results showing that the proposed heuristic method is able to find solutions with cost values very close to the optimal ones for a real nation-wide network and considering a realistic fiber link capacity of 80 wavelengths. Moreover, when compared with other approaches used in the problem variants close to the one addressed here, our heuristic is shown to compute solutions, on average, with better cost values and/or in shorter runtimes.