Exact approaches to the single-source network loading problem

This article considers the network design problem that searches for a minimum-cost way of installing capacities on the edges of a network to simultaneously route a flow from a given access point to a subset of nodes representing customers with positive demands. We first consider compact and exponential-sized Mixed Integer Programming (MIP) formulations of the problem and provide their theoretical and computational comparison. We also consider a stronger disaggregated flow formulation. To solve the problem in practice, we project out the flow variables and generate Benders cuts within a branch-and-cut framework. To the best of our knowledge, the combination of Benders approach and this specific disaggregation has not been considered so far. In an extensive computational study, we compare the performance of compact MIP models against a textbook implementation and several normalization variants of Benders decomposition. We introduce a set of 32 real-world instances and use these, together with 64 other instances from the literature, to test our approaches. The results show that our branch-and-cut approach outperforms the best performing compact formulation leading to the best exact algorithm today for solving the considered dataset. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 59(1), 89-106 2012