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

Ashwin Arulselvan, Mohsen Rezapour, Wolfgang A. Welz

Research output: Contribution to journalArticle

24 Downloads (Pure)


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.
Original languageEnglish
Number of pages31
JournalINFORMS Journal on Computing
Publication statusAccepted/In press - 17 Jan 2017


  • facility location
  • buy at bulk
  • brand price and cut algorith
  • optical access networks

Fingerprint Dive into the research topics of 'Models and exact approaches for designing multi-sink buy-at-bulk networks'. Together they form a unique fingerprint.

  • Profiles

    Cite this