Solving the steiner tree problem with revenues, budget and hop constraints to optimality

Name: Solving the steiner tree problem with revenues, budget and hop constraints to optimality
Author: Layeb, S. B., Hajri, I., Haouari, Mohamed

İsim	Solving the steiner tree problem with revenues, budget and hop constraints to optimality
Yazar	Layeb, S. B., Hajri, I., Haouari, Mohamed
Basım Tarihi:	2013
Basım Yeri	- IEEE
Konu	Steiner tree, Mixed integer programming, MTZ subtour elimination constraints, Reformulation-linearization technique
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	2-s2.0-84881411023
Kayıt Numarası	ed0ea209-9edc-4e73-8481-595e7c1b0cd0
Lokasyon	Industrial Engineering
Tarih	2013
Notlar	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Örnek Metin	We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as well as a preset budget and hop, the STPRBH seeks to find a subtree that includes the root node and maximizes the sum of the total edge revenues respecting the budget and hop constraints. These constraints impose limits on the total cost of the network and the number of edges between any vertex and the root. Not surprisingly, the STPRBH is NP-hard. For this challenging network design problem that arises in telecommunication settings and multicast routing, we present several polynomial size formulations. We propose an enhanced formulation based on the classical work of Miller, Tucker, and Zemlin by using additional set of variables representing the rank-order of visiting the nodes. Also, we investigate a new formulation for the STPRBH by tailoring a partial rank-1 of the Reformulation-Linearization Technique. Extensive results are exhibited using a set of benchmark instances to compare the proposed formulations by using a general purpose MIP solver.
DOI	10.1109/ICMSAO.2013.6552674

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

Solving the steiner tree problem with revenues, budget and hop constraints to optimality

Yazar Layeb, S. B., Hajri, I., Haouari, Mohamed

Basım Tarihi 2013

Basım Yeri - IEEE

Konu Steiner tree, Mixed integer programming, MTZ subtour elimination constraints, Reformulation-linearization technique

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 2-s2.0-84881411023

Kayıt Numarası ed0ea209-9edc-4e73-8481-595e7c1b0cd0

Lokasyon Industrial Engineering

Tarih 2013

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

Örnek Metin We investigate the Steiner tree problem with revenues, budget and hop constraints (STPRBH) on graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, nodes revenues, as well as a preset budget and hop, the STPRBH seeks to find a subtree that includes the root node and maximizes the sum of the total edge revenues respecting the budget and hop constraints. These constraints impose limits on the total cost of the network and the number of edges between any vertex and the root. Not surprisingly, the STPRBH is NP-hard. For this challenging network design problem that arises in telecommunication settings and multicast routing, we present several polynomial size formulations. We propose an enhanced formulation based on the classical work of Miller, Tucker, and Zemlin by using additional set of variables representing the rank-order of visiting the nodes. Also, we investigate a new formulation for the STPRBH by tailoring a partial rank-1 of the Reformulation-Linearization Technique. Extensive results are exhibited using a set of benchmark instances to compare the proposed formulations by using a general purpose MIP solver.

DOI 10.1109/ICMSAO.2013.6552674