HEC Montréal, Canada, 6 - 8 mai 2013
Journées de l'optimisation 2013
HEC Montréal, Canada, 6 — 8 mai 2013
MB10 Localisation et conception de réseaux I / Location and Network Design I
6 mai 2013 15h30 – 17h10
Salle: Nancy et Michel-Gaucher
Présidée par Bernard Gendron
15h30 - 15h55
Lagrangian Relaxation Approaches for Multicommodity Uncapacitated Network Design
We present several algorithms for solving the multicommodity uncapacitated network design problem. We report the results obtained by using different Lagrangian relaxation approaches, a classical specialized dual-ascent method and combinations of these algorithms. We solve the Lagrangian duals by using different variants of non differentiable optimization approaches like (incremental, deflected, projected) subgradient-type methods and (disaggregated, generalized) bundle type methods.
15h55 - 16h20
Primal Heuristic and Lagrangian Relaxation for an Industrial Two-Echelon Location-Distribution Problem
We describe practical methods to solve an industrial location-distribution problem approximately, with solution quality estimates. Solving the problem as a MIP seems difficult. We instead present a multilayer neighbourhood search method and a Lagrangian decomposition method: the former quickly solutions, while the latter proves their quality.
16h20 - 16h45
Benders Decomposition for a Location-Design Problem in Green Wireless Local Area Networks
We consider a problem arising in the design of green (or energy-saving) wireless local area networks (GWLANs). Decisions on both location and capacity dimensioning must be taken simultaneously. We model the problem as an integer program with nonlinear constraints and derive valid inequalities. We handle the nonlinearity of the formulation by developing a Benders decomposition algorithm. We propose various ways to improve the Benders master problem and the feasibility cuts.
16h45 - 17h10
Routing and Wavelength Assignment Problem with Geodesics in Realistic Optical Transport Network Topologies
We present a decomposition approach for solving a variant of the Routing and Wavelength Assignment (RWA) problem. The results show that our approach can find the optimal number of wavelengths for 28 of the 29 realistic optical transport networks tested in a short computing time.