A branch-and-price approach for an integrated capacity dimensioning and demand routing in SDH/WDM networks. (9th May 2011)

• Record Type: Journal Article
• Authors: Balma, Ali; Hadj-Alouane, Nejib Ben; Hadj-Alouane, Atidel Boubaker
• Is Part Of: International journal of business performance and supply chain modelling. Volume 3:Number 1(2011)
• Page Start: 3
• Page End: 19
• Publication Date: 2011-05-09
• Subjects: network design -- capacity dimensioning -- demand routing -- multicommodity -- SDH networks -- WDM networks -- unsplittable flows -- branch and price -- traffic grooming -- mixed integer linear programming -- MILP -- synchronous digital hierarchy -- synchronous optical networks -- SONET -- wavelength division multiplex; Business logistics -- Research -- Periodicals; 658.5005
• Languages: English
• ISSNs: 1758-9401

Abstract

In this paper, we consider the problem of integrated capacity dimensioning and demand routing in SDH/WDM networks, well-known in the telecommunication community as the traffic grooming problem. This problem is generally formulated as an integer linear programme that is typically hard to solve due to the unsplittable nature of channels and their non-uniform sizes. We transform the problem into mixed integer linear programme by relaxing the unsplittability constraints on flow variables. Then, we propose a branch-and-price approach that branches only on capacity variables and generates basic solutions for pricing sub-problems, having a non-zero variable for each separate channel. We also provide expressions for generating basic solutions. We show that the pricing process is polynomial. Since the 'complexity' of the problem depends only on the number of edges, the solution approach is expected to be computationally effective.