Article ID Journal Published Year Pages File Type
4652733 Electronic Notes in Discrete Mathematics 2010 8 Pages PDF
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