An exact algorithm for the Steiner Tree Problem with Delays

Valeria Leggieri; Mohamed Haouari; Chefi Triki

doi:10.1016/j.endm.2010.05.029

An exact algorithm for the Steiner Tree Problem with Delays

Valeria Leggieri^*, Mohamed Haouari, Chefi Triki

^*Corresponding author for this work

Mechanical and Industrial Engineering

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

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.

Original language	English
Pages (from-to)	223-230
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	36
Issue number	C
DOIs	https://doi.org/10.1016/j.endm.2010.05.029
Publication status	Published - Aug 2010

Keywords

Branch-and-Cut
MTZ subtour elimination constraints
Steiner Tree Problem

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2010.05.029

Cite this

@article{13feacd2e4e14d5395f11b49da7c7713,

title = "An exact algorithm for the Steiner Tree Problem with Delays",

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.",

keywords = "Branch-and-Cut, MTZ subtour elimination constraints, Steiner Tree Problem",

author = "Valeria Leggieri and Mohamed Haouari and Chefi Triki",

year = "2010",

month = aug,

doi = "10.1016/j.endm.2010.05.029",

language = "English",

volume = "36",

pages = "223--230",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

T1 - An exact algorithm for the Steiner Tree Problem with Delays

AU - Leggieri, Valeria

AU - Haouari, Mohamed

AU - Triki, Chefi

PY - 2010/8

Y1 - 2010/8

N2 - 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.

AB - 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.

KW - Branch-and-Cut

KW - MTZ subtour elimination constraints

KW - Steiner Tree Problem

UR - http://www.scopus.com/inward/record.url?scp=77954936857&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954936857&partnerID=8YFLogxK

U2 - 10.1016/j.endm.2010.05.029

DO - 10.1016/j.endm.2010.05.029

M3 - Article

AN - SCOPUS:77954936857

SN - 1571-0653

VL - 36

SP - 223

EP - 230

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

IS - C

ER -

An exact algorithm for the Steiner Tree Problem with Delays

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this