|
ISCRIZIONE |
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
