4 Presentations

• 
  03:30 PM - 03:55 PM

  Lagrangian Relaxation Approaches for Multicommodity Uncapacitated Network Design

  • Enrico Gorgone, presenter, Università della Calabria
  • Bernard Gendron, Université de Montréal, CIRRELT
  • Antonio Frangioni, Dipartimento di informatica, Universita di Pisa

  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

  • Paul-Virak Khuong, presenter, Université de Montréal
  • Bernard Gendron, Université de Montréal, CIRRELT

  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

  • Bernard Gendron, presenter, Université de Montréal, CIRRELT
  • Rosario G. Garroppo, Dipartimento di Ingegneria dell'Informazione, Universita degli Studi di Pisa, Pisa, Italy
  • Gianfranco Nencioni, Dipartimento di Ingegneria dell'Informazione, Universita degli Studi di Pisa, Pisa, Italy
  • Maria Grazia Scutellà, Dipartimento di Informatica, Universita degli Studi di Pisa, Pisa, Italy
  • Luca Tavanti, Dipartimento di Ingegneria dell'Informazione, Universita degli Studi di Pisa, Pisa, Italy

  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

  • Martin Cousineau, presenter, McGill University
  • Sylvain Perron, GERAD, HEC Montréal
  • Gilles Caporossi, GERAD, HEC Montréal
  • Marcia Paiva, Federal University of Espirito Santo
  • Marcelo Segatto, Federal University of Espirito Santo

  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.