Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652733 | Electronic Notes in Discrete Mathematics | 2010 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics