A ring-mesh topology design problem for optical transport networks |
| |
Authors: | Youngjin Kim Youngho Lee Junghee Han |
| |
Institution: | (1) Department of Industrial Systems and Information Engineering, Korea University, Sung-Buk Ku Anam Dong 5-1, Seoul, 136-701, Republic of Korea;(2) College of Business Administration, Kangwon National University, Hyoja-dong, Chunchon-shi, Kangwon-do, 200-701, Republic of Korea |
| |
Abstract: | This paper deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The
problem seeks to find an optimal clustering of traffic demands in the network such that the total cost of optical add-drop
multiplexer (OADM) and optical cross-connect (OXC) is minimized, while satisfying the OADM ring capacity constraint, the node
cardinality constraint, and the OXC capacity constraint. We formulate the problem as an integer programming model and propose
several alternative modeling techniques designed to improve the mathematical representation of the problem. We then develop
various classes of valid inequalities to tighten the mathematical formulation of the problem and describe an algorithmic approach
that coordinates tailored routines with a commercial solver CPLEX. We also propose an effective tabu search procedure for
finding a good feasible solution as well as for providing a good incumbent solution for the column generation based heuristic
procedure that enhances the solvability of the problem. Computational results exhibit the viability of the proposed method. |
| |
Keywords: | Optical transport network Ring-mesh topology Integer programming Tabu search Column generation Valid inequality |
本文献已被 SpringerLink 等数据库收录! |
|