Tight compact models and comparative analysis for the prize collecting Steiner tree problem

Name: Tight compact models and comparative analysis for the prize collecting Steiner tree problem
Author: Haouari, Mohamed, Layeb, S. B., Sherali, H. D.

İsim	Tight compact models and comparative analysis for the prize collecting Steiner tree problem
Yazar	Haouari, Mohamed, Layeb, S. B., Sherali, H. D.
Basım Tarihi:	2013-03
Basım Yeri	- Elsevier
Konu	Steiner tree, MTZ subtour elimination constraints, Reformulation–Linearization Technique (RLT), Mixed-integer programming
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0166-218X
Kayıt Numarası	118d13e6-c7c2-4e0a-9399-c1732e185247
Lokasyon	Industrial Engineering
Tarih	2013-03
Notlar	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Örnek Metin	We investigate a generalized version of the prize collecting Steiner tree problem (PCSTP), where each node of a given weighted graph is associated with a prize as well as a penalty cost. The problem is to find a tree spanning a subset of nodes that collects a total prize not less than a given quota Q, such that the sum of the weights of the edges in the tree plus the sum of the penalties of those nodes that are not covered by the tree is minimized. We formulate several compact mixed-integer programming models for the PCSTP and enhance them by appending valid inequalities, lifting constraints, or reformulating the model using the Reformulation–Linearization Technique (RLT). We also conduct a theoretical comparison of the relative strengths of the associated LP relaxations. Extensive results are presented using a large set of benchmark instances to compare the different formulations. In particular, a proposed hybrid compact formulation approach is shown to provide optimal or very near-optimal solutions for instances having up to 2500 nodes and 3125 edges.
DOI	10.1016/j.dam.2011.09.012
Cilt	161

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Tight compact models and comparative analysis for the prize collecting Steiner tree problem

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

Basım Tarihi 2013-03

Basım Yeri - Elsevier

Konu Steiner tree, MTZ subtour elimination constraints, Reformulation–Linearization Technique (RLT), Mixed-integer programming

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0166-218X

Kayıt Numarası 118d13e6-c7c2-4e0a-9399-c1732e185247

Lokasyon Industrial Engineering

Tarih 2013-03

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

Örnek Metin We investigate a generalized version of the prize collecting Steiner tree problem (PCSTP), where each node of a given weighted graph is associated with a prize as well as a penalty cost. The problem is to find a tree spanning a subset of nodes that collects a total prize not less than a given quota Q, such that the sum of the weights of the edges in the tree plus the sum of the penalties of those nodes that are not covered by the tree is minimized. We formulate several compact mixed-integer programming models for the PCSTP and enhance them by appending valid inequalities, lifting constraints, or reformulating the model using the Reformulation–Linearization Technique (RLT). We also conduct a theoretical comparison of the relative strengths of the associated LP relaxations. Extensive results are presented using a large set of benchmark instances to compare the different formulations. In particular, a proposed hybrid compact formulation approach is shown to provide optimal or very near-optimal solutions for instances having up to 2500 nodes and 3125 edges.

DOI 10.1016/j.dam.2011.09.012

Cilt 161