Back to Search

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

Title	The Steiner tree problem with delays: a compact formulation and reduction procedures
Author	Leggieri, V., Haouari, Mohamed, Triki, C.
Publication Date:	2014-02-19
Publication Place	- Elsevier
Subject	Steiner tree problem, MTZ subtour elimination constraints, Reduction techniques
Type	Periodical
Language	English
Digital	Yes
Manuscript	No
Library:	Özyeğin University
Library Asset ID	1872-6771
Record ID	2e2831de-9d7e-4471-895c-2c43c6d5ea98
Library Location	Industrial Engineering
Date	2014-02-19
Sample Text	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

View in source Özyeğin University Özyeğin University - Historical works, archives, and periodicals search engine

Özyeğin University

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

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

Publication Date 2014-02-19

Publication Place - Elsevier

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

Type Periodical

Language English

Digital Yes

Manuscript No

Library Özyeğin University

Library Asset ID 1872-6771

Record ID 2e2831de-9d7e-4471-895c-2c43c6d5ea98

Library Location Industrial Engineering

Date 2014-02-19

Sample Text 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