Premium
Lagrangean decomposition/relaxation for the routing and wavelength assignment problem
Author(s) -
Thiongane Babacar
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20437
Subject(s) - subgradient method , mathematical optimization , relaxation (psychology) , path (computing) , node (physics) , computation , shortest path problem , arc routing , decomposition , column generation , mathematics , enhanced data rates for gsm evolution , computer science , routing (electronic design automation) , algorithm , combinatorics , graph , physics , psychology , social psychology , computer network , ecology , telecommunications , quantum mechanics , biology , programming language
This work deals with solving the Routing and Wavelength Assignment problem where the number of accepted connections is to be maximized. Lagrangean decomposition as well as Lagrangean relaxation are studied for both node‐arc formulations and arc‐path formulation. It is shown that relaxing the demand constraints yields an edge‐disjoint path problem with profits that is NP‐hard, while the Lagrangean problem obtained when the clash constraints are relaxed becomes a shortest path problem or a 0–1 linear knapsack problem, depending on the formulation used. Moreover, it is shown that the Lagrangean decomposition is not stronger than the Lagrangean relaxation of the demand constraints. We also propose a subgradient algorithm to solve the Lagrangean dual obtained by relaxing the clash constraints. Numerical results demonstrate a high quality of Lagrangean dual bounds with fast computation time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012