Decomposition for Network Design

Prof. Bernard Gendron
Computer Science and Operations Research, Université De Montréal and CIRRELT

20 hours, 5 credits

June 25 - June 29, 2012

Dipartimento di Ingegneria dell'Informazione: Elettronica, Informatica, Telecomunicazioni, via Caruso, meeting room, ground floor

Contacts: Ing. Rosario Garroppo

Abstract

Network design applications are prevalent in telecommunications, transportation and logistics. In this series of lessons, we focus on mathematical programming approaches for solving large-scale network design problems. We present the underlying theory and the implementation challenges of several classes of methods: Lagrangian relaxation, Benders decomposition, cutting-plane (or row generation), column generation, column-and-row generation, branch-and-(bound, cut, price). We consider the multicommodity capacitated network design problem, a generic model that captures three important features of network design applications: the interplay between investment and operational costs, the multicommodity aspect, and the presence of capacity constraints.

Syllabus

• Introduction to network design and overview of decomposition in mathematical programming
  
• Lagrangian relaxation for network design
  
• Benders decomposition for network design
  
• Cutting-plane methods for network design
  
• Column generation methods for network design
  
• Column-and-row generation methods for network design
  
• Branch-and-X and filtering algorithms for network design