Solving the Discrete Cost Multicommodity Network Design Problem to Optimality

Multicommodity Network Design problems are a challenging class of problems that arises in the strategic and tactical planning processes and has many applications mainly in the fields of telecommunication and supply chain. Thus, solving this interesting NP-hard problem is fundamental for the profitable business of network operators. In this paper, we focus on a variant of the Discrete Cost Multicommodity Network Design Problem, with multiple discrete facilities (corresponding to different technologies) that could be installed on the edges. Each facility is bidirectional and has prefixed discrete capacity and cost. For this problem, we present a tailored Benders decomposition approach using an arc-flow based formulation and we strengthen it by adding some valid inequalities. Computational experimentations conducted on both randomly generated and real-world instances are reported.