@inproceedings{ea9100985d0a4631a515f76a20d47823,
title = "Branch-and-Cut Algorithms for Steiner Tree Problems with Privacy Conflicts",
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.",
keywords = "Branch-and-cut, Information privacy conflicts, Integer programming, Steiner tree problem, Telecommunications",
author = "Alessandro Hill and Stefan Vo{\~A}Ÿ and Roberto Baldacci",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 25th International Computing and Combinatorics Conference, COCOON 2019 ; Conference date: 29-07-2019 Through 31-07-2019",
year = "2019",
doi = "10.1007/978-3-030-26176-4_22",
language = "English",
isbn = "9783030261757",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "266--278",
editor = "Ding-Zhu Du and Zhenhua Duan and Cong Tian",
booktitle = "Computing and Combinatorics - 25th International Conference, COCOON 2019, Proceedings",
address = "Germany",
}