Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint

Name: Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint
Author: Haouari, Mohamed, Layeb, S. B., Sherali, H. D.

İsim	Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint
Yazar	Haouari, Mohamed, Layeb, S. B., Sherali, H. D.
Basım Tarihi:	2010-08-01
Basım Yeri	- Elsevier
Konu	Steiner Tree, MTZ subtour elimination constraints, Reformulation-Linearization technique, Mixed Integer Programming
Tür	Belge
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1571-0653
Kayıt Numarası	5be156d6-e286-448c-8c53-a9ef8608c81b
Lokasyon	Industrial Engineering
Tarih	2010-08-01
Notlar	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Örnek Metin	This paper investigates the quota version of the Prize Collecting Steiner Tree Problem (PCSTP) on a graph as a generalization of the well-known Steiner tree problem. For this challenging network design problem that arises in telecommunication settings, we present three MIP formulations: (a) the first one is a compact Miller-Tucker-Zemlin (MTZ-) based formulation, (b) the second one is derived through lifting the MTZ constraints, and (c) the third one is based on the RLT technique. We report the results of extensive computational experiments on large PCSTP instances, having up to 2500 nodes using a general-purpose MIP solver.
DOI	10.1016/j.endm.2010.05.063
Cilt	36

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint

Yazar Haouari, Mohamed, Layeb, S. B., Sherali, H. D.

Basım Tarihi 2010-08-01

Basım Yeri - Elsevier

Konu Steiner Tree, MTZ subtour elimination constraints, Reformulation-Linearization technique, Mixed Integer Programming

Tür Belge

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1571-0653

Kayıt Numarası 5be156d6-e286-448c-8c53-a9ef8608c81b

Lokasyon Industrial Engineering

Tarih 2010-08-01

Notlar Due to copyright restrictions, the access to the full text of this article is only available via subscription.

Örnek Metin This paper investigates the quota version of the Prize Collecting Steiner Tree Problem (PCSTP) on a graph as a generalization of the well-known Steiner tree problem. For this challenging network design problem that arises in telecommunication settings, we present three MIP formulations: (a) the first one is a compact Miller-Tucker-Zemlin (MTZ-) based formulation, (b) the second one is derived through lifting the MTZ constraints, and (c) the third one is based on the RLT technique. We report the results of extensive computational experiments on large PCSTP instances, having up to 2500 nodes using a general-purpose MIP solver.

DOI 10.1016/j.endm.2010.05.063

Cilt 36