Exact Approaches for Network Design Problems with Relays

Markus Leitner (), Ivana Ljubić (), Martin Riedler () and Mario Ruthmair ()
Additional contact information
Markus Leitner: Department of Statistics and Operations Research, University of Vienna, 1010 Vienna, Austria
Ivana Ljubić: ESSEC Business School of Paris, 95021 Cergy-Pontoise, France
Martin Riedler: Institute of Logic and Computation, TU Wien, 1040 Vienna, Austria
Mario Ruthmair: Department of Statistics and Operations Research, University of Vienna, 1010 Vienna, Austria

INFORMS Journal on Computing, 2019, vol. 31, issue 1, 171-192

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 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0820 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:31:y:2019:i:1:p:171-192

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().