03:30 PM - 03:55 PM
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.
03:55 PM - 04:20 PM
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.
04:20 PM - 04:45 PM
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.
04:45 PM - 05:10 PM
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.