Decomposition Methods for Network Design

Network design applications are prevalent in transportation and logistics. We consider the multicommodity capacitated fixed-charge network design problem (MCND), 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. We focus on mathematical programming approaches for the MCND and present three classes of methods that have been used to solve large-scale instances of the MCND: a cutting-plane method, a Benders decomposition algorithm, and Lagrangian relaxation approaches.