Formulations and Benders Decomposition based Procedures for the Discrete Cost Multicommodity Network Design Problem

Abstract

Multicommodity Network Design problems arise in a wide range of fields such as telecommunications, computer networks, supply chain and transportation. In this paper, we consider the Discrete Cost Multicommodity Network Design problem (DCMNDP) with several discrete facilities available for installation on each connection/edge. The DCMNDP requires the installation of at most one facility on each edge that allows routing the multicommodity flow demands in order to minimize the sum of the fixed facility installation costs. To solve the DCMNDP to optimality, we have tailored a Benders decomposition based procedure that we apply to two different formulations, namely the widely used arc-flow based formulation and the arc-path based formulation. This latter formulation is characterized by an exponential number of variables whose resolution requires the use of column generation as well as cut generation algorithms. An experimental computational study is conducted on real-world instances to compare the performance of the proposed formulations. The obtained results illustrate the effectiveness of applying Benders decomposition on the arc-path formulation.