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

Authors: Ali Balma, Nejib Ben Hadj-Alouane, Atidel Boubaker Hadj-Alouane

Addresses: OASIS, Ecole Nationale d'Ingenieurs de Tunis, Le Belvedere BP37, 1002 Tunis, Tunisia; Tunisie Telecom, Cite Ennassim, avenue du Japon, Montplaisir, 1073 Tunis, Tunisia. ' OASIS, Ecole Nationale d'Ingenieurs de Tunis, Le Belvedere BP37, 1002 Tunis, Tunisia; Ecole Nationale des Sciences de l'Informatique, 2010 Manouba, Tunisia. ' OASIS, Ecole Nationale d'Ingenieurs de Tunis, Le Belvedere BP37, 1002 Tunis, Tunisia

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.

DOI: 10.1504/IJBPSCM.2011.039970

International Journal of Business Performance and Supply Chain Modelling, 2011 Vol.3 No.1, pp.3 - 19

Published online: 30 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article