首页> 外文会议>International Computing and Combinatorics Conference >Branch-and-Cut Algorithms for Steiner Tree Problems with Privacy Conflicts
【24h】

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

机译:具有隐私冲突的Steiner树问题的分支剪切算法

获取原文

摘要

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.
机译:在本文中,我们在图中提出了著名的Steiner树问题的两个新颖变体,这些变体是由安全战略电信网络设计中的应用所激发的。两种网络优化模型都要求树的总边缘成本最小,该树通过可选地包括中间Steiner节点将一组预先指定的终端节点连接到专用根节点。考虑了成对的冲突终端之间的两种类型的隐私冲突:(I)从根到终端的路径必须不包括冲突终端,并且(II)冲突终端必须位于树的单独分支上。我们开发非紧凑型整数编程公式,并精心设计分支剪切算法。我们并入了特定于问题的有效不等式,这些不等式对于解决这些问题至关重要,并在这些割线和诱导的多面体之间建立优势关系。在多种基于SteinLib的测试实例上评估了切割平面相对于双重边界的有效性和精确算法的性能。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号