A branch-and-price approach for an integrated capacity dimensioning and demand routing in SDH/WDM networks

Ali Balma, Nejib Ben Hadj-Alouane and Atidel Boubaker Hadj-Alouane

International Journal of Business Performance and Supply Chain Modelling, 2011, vol. 3, issue 1, 3-19

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.

Keywords: 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. (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=39970 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijbpsc:v:3:y:2011:i:1:p:3-19

Access Statistics for this article

More articles in International Journal of Business Performance and Supply Chain Modelling from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().