Journées de l'optimisation 2007 Optimizations days

We present a decomposition formulation for the grooming routing and wavelength assignment problem (GRWA) and an associated rounding-off heuristic. We compare the quality of the solutions obtained with different variable selection criterion.

This work deals with the solving of the routing and wavelength assignment problem where we want to maximize the number of accepted connections given a network with a set of demands, while respecting the clash constraints. Many formulations are considered and bounds derived from lagrangean decomposition and lagrangean relaxation are compared. For both formulations we show that lagrangean decomposition doesn't yield stronger bounds than lagrangean relaxation of the demand constraints. Many lagrangean dual problems are solved using a subgradient algorithm in which a procedure to derive primal feasible solution is embedded. Numerical results showing the efficiency of the lagrangean heuristics are presented.

Broadband wireless with WiMAX (Worldwide Interoperability for Microwave Access) is changing the perspective of wireless communications. The problem addressed in this paper is the planning of core WiMAX networks. First the optimization algorithm assigns subscribers to the potential base stations, and then tries to fulfill subscribers’ demand with minimum number of subchannels. To gain the best out of subchannels’ dynamic property, they are grouped in different beams and the movement in the algorithm is defined by changing beam direction.

In this paper, we propose a model for the global design problem of wavelength division multiplexing (WDM) networks involving the traffic grooming as a management technique. This problem consists in finding the number of fibers between each pair of nodes, selecting the configuration of each node related to the number of transponders, choosing the virtual topology which is the set of the lightpaths, rooting these lightpaths over le physical topology, assigning a wavelength to each lightpath, grooming and finally routing the traffic over the lightpaths. Since this problem is NP-hard, we propose heuristics, a local search and a tabu search algorithms to find good solutions for real-size instances. A multi-criteria search is also preformed to optimize several objectives and to find a satisfactory compromise.