Ring-mesh topology design in a SONET-WDM network

This article deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The problem seeks to partition the set of demand pairs to a number of rings and a mesh cluster, and to determine the location of the optical cross-connect system (OXC), while minimizing the total cost of optical add-drop multiplexers (OADMs), OXCs, and fiber links. We formulate this problem as a zero-one integer programming problem. In strengthening the formulation, we develop some valid inequalities for the zero-one quadratic (knapsack) polytope and a column generation formulation that eliminates the symmetry of ring configurations. Also, we prescribe an effective tabu search procedure for finding a good quality feasible solution, which is also used as a starting column for the column generation procedure. Computational results show that the proposed solution procedure provides tight lower and upper bounds within a reasonable time bound.