Author
Haouari, Mohamed, Layeb, S. B., Sherali, H. D.
Publication Date
2013-03
Publication Place
-
Elsevier
Subject
Steiner tree, MTZ subtour elimination constraints, Reformulation–Linearization Technique (RLT), Mixed-integer programming
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
0166-218X
Record ID
118d13e6-c7c2-4e0a-9399-c1732e185247
Library Location
Industrial Engineering
Date
2013-03
Notes
Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Sample Text
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
