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

摘要

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 poly-hedra. 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.