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

In this paper, we consider the problem of simultaneous capacity dimensioning and demand routing in SDH/WDM networks, well-known in the telecommunication community as Traffic Grooming Problem. This problem is generally formulated as an Integer Linear Program that has been shown to be NP-complete and especially hard to solve due to the unsplittable nature of channels and their non uniform sizes. We transform the problem into Mixed Integer Linear Program by relaxing unsplittability constraints on flow variables. Then, we give 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 (of relevance for unsplittable flows). Also, we provide conditions on how these bases are generated. We further show that our process is polynomial. Since the ldquocomplexityrdquo of the problem depends only on the number of edges, the solution approach is expected to be computationally effective.