Branch-and-Cut Algorithms for Steiner Tree Problems with Privacy Conflicts

Alessandro Hill*, Stefan Voß, Roberto Baldacci

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

Abstract

In this paper we propose two novel variants of the well-known Steiner tree problem in graphs that are motivated by applications in secure strategic telecommunication network design. Both network optimization models ask for a tree of minimal total edge cost that connects a pre-specified set of terminal nodes to a dedicated root node by optionally including intermediate Steiner nodes. Two types of privacy conflicts between pairs of conflicting terminals are considered: (I) The path from the root to a terminal must not include the conflicting terminal, and (II) conflicting terminals have to be on separate branches of the tree. We develop non-compact integer programming formulations and elaborate branch-and-cut algorithms. We incorporate problem specific valid inequalities that are crucial in order to solve these problems, and establish dominance relationships between these cuts and the induced polyhedra. The effectiveness of the cutting planes with respect to the dual bound and the performance of the exact algorithm are assessed on a diverse set of SteinLib-based test instances.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings
EditorsDing-Zhu Du, Zhenhua Duan, Cong Tian
PublisherSpringer Verlag
Pages266-278
Number of pages13
ISBN (Print)9783030261757
DOIs
Publication statusPublished - 2019
Externally publishedYes
Event25th International Computing and Combinatorics Conference, COCOON 2019 - Xi'an, China
Duration: 29 Jul 201931 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11653 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Computing and Combinatorics Conference, COCOON 2019
Country/TerritoryChina
CityXi'an
Period29/07/1931/07/19

Keywords

  • Branch-and-cut
  • Information privacy conflicts
  • Integer programming
  • Steiner tree problem
  • Telecommunications

Fingerprint

Dive into the research topics of 'Branch-and-Cut Algorithms for Steiner Tree Problems with Privacy Conflicts'. Together they form a unique fingerprint.

Cite this