Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 43-53 |
Number of pages | 11 |
Journal | Photonic Network Communications |
Volume | 20 |
Issue number | 1 |
DOIs | |
Publication status | Published - 2010 Aug |
Keywords
- Column generation
- Integer programming
- Optical transport network
- Ring-mesh topology
- Tabu search
- Valid inequality
ASJC Scopus subject areas
- Software
- Atomic and Molecular Physics, and Optics
- Hardware and Architecture
- Computer Networks and Communications
- Electrical and Electronic Engineering