The Steiner tree problem with delays: a compact formulation and reduction procedures

Name: The Steiner tree problem with delays: a compact formulation and reduction procedures
Author: Leggieri, V., Haouari, Mohamed, Triki, C.

İsim	The Steiner tree problem with delays: a compact formulation and reduction procedures
Yazar	Leggieri, V., Haouari, Mohamed, Triki, C.
Basım Tarihi:	2014-02-19
Basım Yeri	- Elsevier
Konu	Steiner tree problem, MTZ subtour elimination constraints, Reduction techniques
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1872-6771
Kayıt Numarası	2e2831de-9d7e-4471-895c-2c43c6d5ea98
Lokasyon	Industrial Engineering
Tarih	2014-02-19
Örnek Metin	This paper investigates the Steiner Tree Problem with Delays (STPD), a variation of the classical Steiner Tree problem that arises in multicast routing. We propose an exact solution approach that is based on a polynomial-size formulation for this challenging NP-hard problem. The LP relaxation of this formulation is enhanced through the derivation of new lifted Miller Tucker Zemlin subtour elimination constraints. Furthermore, we present several preprocessing techniques for both reducing the problem size and tightening the LP relaxation. Finally, we report the results of extensive computational experiments on instances with up to 1000 nodes. These results attest to the efficacy of the combination of the enhanced formulation and reduction techniques.
DOI	10.1016/j.dam.2011.07.008
Cilt	164

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

The Steiner tree problem with delays: a compact formulation and reduction procedures

Yazar Leggieri, V., Haouari, Mohamed, Triki, C.

Basım Tarihi 2014-02-19

Basım Yeri - Elsevier

Konu Steiner tree problem, MTZ subtour elimination constraints, Reduction techniques

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1872-6771

Kayıt Numarası 2e2831de-9d7e-4471-895c-2c43c6d5ea98

Lokasyon Industrial Engineering

Tarih 2014-02-19

Örnek Metin This paper investigates the Steiner Tree Problem with Delays (STPD), a variation of the classical Steiner Tree problem that arises in multicast routing. We propose an exact solution approach that is based on a polynomial-size formulation for this challenging NP-hard problem. The LP relaxation of this formulation is enhanced through the derivation of new lifted Miller Tucker Zemlin subtour elimination constraints. Furthermore, we present several preprocessing techniques for both reducing the problem size and tightening the LP relaxation. Finally, we report the results of extensive computational experiments on instances with up to 1000 nodes. These results attest to the efficacy of the combination of the enhanced formulation and reduction techniques.

DOI 10.1016/j.dam.2011.07.008

Cilt 164