Large scale optimization in survivable WDM mesh networks: Tutorial proposal (DRCN 2009)

Design and planning of survivable WDM networks involve different decision and optimization problems under network, traffic, and cost constraints. The high bandwidth brought by WDM access technology has incited network operators to extensive deployment of WDM in both access and backbone networks. Edges of networks have been pushed and transport capacity significantly increased, making the design and planning tasks harder. Consequently, efficient and scalable tools are, more than ever, needed to help network designers. Most of the design and planning problems arising in survivable optical WDM network are large scale optimization and hard combinatorial ones that cannot be tackled efficiently with the classical integer linear programming (ILP) approaches. The column generation (CG) technique is an efficient optimization tool which has been shown to be very effective for solving particular classes of large scale systems. Indeed, combined with classical ILP tools, the CG technique offers a valuable tool for the design of highly efficient global search heuristics with an indication on the distance to the globally optimal solution when exact solution is not possible. However, it requires special care at the mathematical modeling step. The objective of this tutorial is to provide in-depth learning on the use of CG and ILP tools throughout different network design examples arising in survivable WDM networks, showing that such tools are highly efficient and scalable.