Exact approaches for the directed network design problem with relays

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

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum cost network that enables the communication of a given set of origin-destination pairs. Thereby, expensive signal regeneration devices need to be placed to cover communication distances exceeding a predefined threshold. Applications of the DNDPR arise in telecommunications and transportation. We propose two new integer programming formulations for the DNDPR. The first one is a flow-based formulation with a pseudo-polynomial number of variables and constraints and the second is a cut-based formulation with an exponential number of constraints. Fractional distance values are handled efficiently by augmenting both models with an exponentially-sized set of infeasible path constraints. We develop branch-and-cut algorithms and also consider valid inequalities to strengthen the obtained dual bounds and to speed up convergence. The results of our extensive computational study on diverse sets of benchmark instances show that our algorithms outperform the previous state-of-the-art method based on column generation.
Original languageEnglish
Number of pages17
JournalOmega
DOIs
Publication statusAccepted/In press - 2019

Fingerprint

Network design
Communication
Polynomials
Destination
Valid inequalities
Regeneration
Benchmark
Integer programming
Column generation
Costs
Telecommunications

Keywords

  • Integer Programming
  • Networks
  • Layered Graphs
  • Telecommunications

Cite this

Leitner, M. ; Ljubic, Ivana ; Ruthmair, Mario ; Riedler, Martin. / Exact approaches for the directed network design problem with relays. In: Omega. 2019.
@article{61ddb279d0884e4abb11fb9227b9be03,
title = "Exact approaches for the directed network design problem with relays",
abstract = "We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum cost network that enables the communication of a given set of origin-destination pairs. Thereby, expensive signal regeneration devices need to be placed to cover communication distances exceeding a predefined threshold. Applications of the DNDPR arise in telecommunications and transportation. We propose two new integer programming formulations for the DNDPR. The first one is a flow-based formulation with a pseudo-polynomial number of variables and constraints and the second is a cut-based formulation with an exponential number of constraints. Fractional distance values are handled efficiently by augmenting both models with an exponentially-sized set of infeasible path constraints. We develop branch-and-cut algorithms and also consider valid inequalities to strengthen the obtained dual bounds and to speed up convergence. The results of our extensive computational study on diverse sets of benchmark instances show that our algorithms outperform the previous state-of-the-art method based on column generation.",
keywords = "Integer Programming, Networks, Layered Graphs, Telecommunications",
author = "M. Leitner and Ivana Ljubic and Mario Ruthmair and Martin Riedler",
year = "2019",
doi = "10.1016/j.omega.2018.11.014",
language = "English",
journal = "Omega",
issn = "0305-0483",
publisher = "Elsevier BV",

}

Exact approaches for the directed network design problem with relays. / Leitner, M.; Ljubic, Ivana; Ruthmair, Mario; Riedler, Martin.

In: Omega, 2019.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Exact approaches for the directed network design problem with relays

AU - Leitner, M.

AU - Ljubic, Ivana

AU - Ruthmair, Mario

AU - Riedler, Martin

PY - 2019

Y1 - 2019

N2 - We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum cost network that enables the communication of a given set of origin-destination pairs. Thereby, expensive signal regeneration devices need to be placed to cover communication distances exceeding a predefined threshold. Applications of the DNDPR arise in telecommunications and transportation. We propose two new integer programming formulations for the DNDPR. The first one is a flow-based formulation with a pseudo-polynomial number of variables and constraints and the second is a cut-based formulation with an exponential number of constraints. Fractional distance values are handled efficiently by augmenting both models with an exponentially-sized set of infeasible path constraints. We develop branch-and-cut algorithms and also consider valid inequalities to strengthen the obtained dual bounds and to speed up convergence. The results of our extensive computational study on diverse sets of benchmark instances show that our algorithms outperform the previous state-of-the-art method based on column generation.

AB - We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum cost network that enables the communication of a given set of origin-destination pairs. Thereby, expensive signal regeneration devices need to be placed to cover communication distances exceeding a predefined threshold. Applications of the DNDPR arise in telecommunications and transportation. We propose two new integer programming formulations for the DNDPR. The first one is a flow-based formulation with a pseudo-polynomial number of variables and constraints and the second is a cut-based formulation with an exponential number of constraints. Fractional distance values are handled efficiently by augmenting both models with an exponentially-sized set of infeasible path constraints. We develop branch-and-cut algorithms and also consider valid inequalities to strengthen the obtained dual bounds and to speed up convergence. The results of our extensive computational study on diverse sets of benchmark instances show that our algorithms outperform the previous state-of-the-art method based on column generation.

KW - Integer Programming

KW - Networks

KW - Layered Graphs

KW - Telecommunications

U2 - 10.1016/j.omega.2018.11.014

DO - 10.1016/j.omega.2018.11.014

M3 - Article

JO - Omega

JF - Omega

SN - 0305-0483

ER -