An exact algorithm for the Steiner tree problem with delays
Type :
Conference paper
Publication Status :
published
Access :
restrictedAccess
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.
Source :
Electronic Notes in Discrete Mathematics
Date :
2010-08-01
Volume :
36
Publisher :
Elsevier
URI
http://hdl.handle.net/10679/183http://www.sciencedirect.com/science/article/pii/S1571065310000302
Collections
Share this page