We present a review of column generation formulations for the Routing and Wavelength Assignment RWA problem with the objective of minimizing the blocking rate. Several improvements are proposed together with a comparison of the different formulations with respect to the quality of their continuous relaxation bounds and their computing solution ease.

We consider the problem of traffic grooming of low-rate traffic circuits in WDM rings where circuits are associated with a set of heterogeneous granularities. While networks are no longer limited by transmission bandwidth, the key issue in WDM network design has evolved towards the processing capabilities of electronic switches, routers and multiplexers. Therefore, we focus here on traffic grooming with minimum interconnecting equipment cost. We first formulate the problem as an integer linear programming (ILP) or a mixed integer linear programming (MILP) problem depending on the design specifications: UPSR vs BLSR, fixed vs variable wavelength capacities, non bifurcated vs bifurcated flows, wavelength continuity vs possible signal regeneration on a different wavelength. Considering the case study of the second SONET ring generation with MSPP like interconnection equipments, we define the cost by a function of the number of transport blades, taking into account that the number of MSPP transport blades makes up a significant portion of the overall network design cost. Using the CPLEX linear programming package, we next compare the optimal solutions of the ILP or MILP programs for different design assumptions, including the classical ring network design scheme with a single hub where the lightpaths directly connect the hub to all other nodes.

We present different formulations, including a column generation formulation for solving the GRWA - Grooming, Routing and Wavelength Assignment in optical networks. Traffic grooming is defined as the problem of how to pack different low-rate traffic streams into higher speed streams. In optical networks, the traffic grooming is often coupled with the RWA problem, i.e., the problem of routing and wavelength assignment of the higher speed streams so as to optimize some design objective or minimize the management cost. The resulting problem correspond to the so-called GRWA problem. We will discuss in particular how to formulate and then solve the pricing problem. Preliminary experimental results will also be presented.