Exact Approaches for Network Design Problems with Relays

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

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

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.
LanguageEnglish
Pages171-192
JournalINFORMS Journal on Computing
Volume31
Issue number1
DOIs
Publication statusPublished - 2019

Fingerprint

Linear programming
Telecommunication networks
Network design
Branch-and-price
Destination
Telecommunication network
Regeneration
Heuristics
Mixed integer linear programming

Keywords

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

Cite this

Leitner, M. ; Ljubic, Ivana ; Riedler, Martin ; Ruthmair, Mario. / Exact Approaches for Network Design Problems with Relays. In: INFORMS Journal on Computing. 2019 ; Vol. 31, No. 1. pp. 171-192.
@article{fa8b1182e95f4a22b99e8eb99cd28290,
title = "Exact Approaches for Network Design Problems with Relays",
abstract = "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.",
keywords = "Network design with relays, Telecommunications, Integer programming, Branch-and-price",
author = "M. Leitner and Ivana Ljubic and Martin Riedler and Mario Ruthmair",
year = "2019",
doi = "10.1287/ijoc.2018.0820",
language = "English",
volume = "31",
pages = "171--192",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",

}

Exact Approaches for Network Design Problems with Relays. / Leitner, M.; Ljubic, Ivana; Riedler, Martin; Ruthmair, Mario.

In: INFORMS Journal on Computing, Vol. 31, No. 1, 2019, p. 171-192.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Exact Approaches for Network Design Problems with Relays

AU - Leitner, M.

AU - Ljubic, Ivana

AU - Riedler, Martin

AU - Ruthmair, Mario

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Network design with relays

KW - Telecommunications

KW - Integer programming

KW - Branch-and-price

U2 - 10.1287/ijoc.2018.0820

DO - 10.1287/ijoc.2018.0820

M3 - Article

VL - 31

SP - 171

EP - 192

JO - INFORMS Journal on Computing

T2 - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 1

ER -