Models and exact approaches for designing multi-sink buy-at-bulk networks

Arulselvan, Ashwin and Rezapour, Mohsen and Welz, Wolfgang A. (2017) Models and exact approaches for designing multi-sink buy-at-bulk networks. INFORMS Journal on Computing. ISSN 1526-5528 (In Press)

[img]
Preview
Text (Arulselvan-etal-INFORMS-2017-Models-and-exact approaches-for-designing-multi-sink-buy)
Arulselvan_etal_INFORMS_2017_Models_and_exact_approaches_for_designing_multi_sink_buy.pdf
Accepted Author Manuscript

Download (660kB)| Preview

    Abstract

    We study a problem that integrates buy-at-bulk network design into the classical facility location problem. We consider a generalization of the facility location problem where multiple clients may share a capacitated network to connect to open facilities instead of requiring direct links. In this problem, we wish to open facilities, build a routing network by installing access cables of different costs and capacities, and route every client demand to an open facility. We provide a path based formulation and we compare it with the natural compact formulation for this problem. We then design an exact branch-price-and-cut algorithm for solving the path based formulation. We study the effect of two families of valid inequalities. In addition to this, we present three different types of primal heuristics and employ a hybrid approach to effectively combine these heuristics in order to improve the primal bounds. We finally report the results of our approach that were tested on a set of real world instances as well as two sets of benchmark instances and evaluate the effects of our valid inequalities and primal heuristics.