A Fiber Routing Problem in Designing Optical Transport Networks with Wavelength Division Multiplexed Systems

In this paper, we consider a fiber routing problem arising from the design of optical transport networks. The problem is to find an optimal routing of multiple rings and an optimal location of wavelength division multiplexed (WDM) systems for carrying demand traffic. This problem can be conceptualized as a Steiner (multiple) ring problem with link capacity constraints. We formulate the problem as a mixed-integer programming model and develop a new branch-and-cut procedure along with preprocessing routines and valid inequalities for optimally solving the problem. Exploiting the inherent special structures of the formulation, we focus on developing strong valid inequalities and devising an effective Tabu search heuristic for solving large-scale problems. Computational results indicate that preprocessing rules and valid inequalities provide a tight lower bound, and in turn reduce the effort required to solve the problem within the framework of the branch-and-cut procedure. Moreover, the proposed Tabu search heuristic works quite well for solving large-scale problems. Motivated by promising computational results, we provide insights into implementing the proposed branch-and-cut procedure for deploying fiber optic networks in practice.