The two-level diameter constrained spanning tree problem

• 成果类型: Article; Proceedings Paper
• 署名作者: Gouveia, Luis; Leitner, Markus; Ljubic, Ivana
• 署名单位: Universidade de Lisboa; University of Vienna; Technische Universitat Wien
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-013-0743-z
• 发表日期: 2015
• 页码: 49-78
• 关键词: survivable network design; steiner trees

摘要

In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements. We first observe that any feasible solution to the 2-DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree. This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer programming formulations, valid inequalities, and symmetry breaking constraints. In particular, we propose a novel modeling approach based on a three-dimensional layered graph. In an extensive computational study we show that a branch-and-cut algorithm based on the latter model is highly effective in practice.