An Exact Algorithm for the Steiner Tree Problem with Delays

详细信息    查看全文

• 作者：Valeria Leggieri ; Mohamed Haouari ; Chefi Triki
• 关键词：Steiner Tree Problem ; MTZ subtour elimination constraints ; Branch-and-Cut
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2010
• 出版时间：1 August 2010
• 年：2010
• 卷：36
• 期：Complete
• 页码：223-230
• 全文大小：237 K

文摘

The Steiner Tree Problem with Delays (STPD) is a variant of the well-known Steiner Tree Problem in which the delay on each path between a source node and a terminal node is limited by a given maximum value. We propose a Branch-and-Cut algorithm for solving this problem using a formulation based on lifted Miller-Tucker-Zemlin subtour elimination constraints. The effectiveness of the proposed algorithm is assessed through computational experiments carried out on dense benchmark instances.