Exact Approaches for Network Design Problems with Relays

M. Leitner, Ivana Ljubic, Martin Riedler, Mario Ruthmair

Research output: Contribution to JournalArticleAcademicpeer-review

322 Downloads (Pure)


In this article we consider the network design problem with relays (NDPR), which gives answers to some important strategic design questions in telecommunication network design. Given a family of origin-destination pairs and a set of existing links these questions are as follows: (1) What are the optimal locations for signal regeneration devices (relays) and how many of them are needed? (2) Could the available infrastructure be enhanced by installing additional links in order to reduce the travel distance and therefore reduce the number of necessary relays?

In contrast to previous work on the NDPR, which mainly focused on heuristic approaches, we discuss exact methods based on different mixed-integer linear programming formulations for the problem. We develop branch-and-price and branch-price-and-cut algorithms that build upon models with an exponential number of variables (and constraints). In an extensive computational study, we analyze the performance of these approaches for instances that reflect different real-world settings. Finally, we also point out the relevance of the NDPR in the context of electric mobility.
Original languageEnglish
Pages (from-to)171-192
Number of pages22
JournalINFORMS Journal on Computing
Issue number1
Early online date8 Jan 2019
Publication statusPublished - Feb 2019


  • Branch-and-price
  • Integer programming
  • Network design with relays
  • Telecommunications


Dive into the research topics of 'Exact Approaches for Network Design Problems with Relays'. Together they form a unique fingerprint.

Cite this