Paper Info
Title
Algorithmic expedients for the Prize Collecting Steiner Tree Problem
Abstract
This paper investigates the Prize Collecting Steiner Tree Problem (PCSTP) on a graph, which is a generalization of the well-known Steiner tree problem. Given a root node, edge costs, node prizes and penalties, as well as a preset quota, the PCSTP seeks to find a subtree that includes the root node and collects a total prize not smaller than the specified quota, while minimizing the sum of the total edge costs of the tree plus the penalties associated with the nodes that are not included in the subtree. For this challenging network design problem that arises in telecommunication settings, we present two valid 0-1 programming formulations and use them to develop preprocessing procedures for reducing the graph size. Also, we design an optimization-based heuristic that requires solving a PCSTP on a specific tree-subgraph. Although, this latter special case is shown to be NP-hard, it is effectively solvable in pseudo-polynomial time. The worst-case performance of the proposed heuristic is also investigated. In addition, we describe new valid inequalities for the PCSTP and embed all the aforementioned constructs in an exact row-generation approach. Our computational study reveals that the proposed approach can solve relatively large-scale PCSTP instances having up to 1000 nodes to optimality.
Year
DOI
Venue
2010
10.1016/j.disopt.2010.01.001
Discrete Optimization
Keywords
Field
DocType
optimization-based heuristic,steiner tree,challenging network design problem,root node,new valid inequality,large-scale pcstp instance,prize collecting steiner tree,valid inequalities,exact row-generation approach,graph size,node prize,reduction techniques,worst-case analysis,edge cost,algorithmic expedient,network design,polynomial time,steiner tree problem
Graph,Heuristic,Mathematical optimization,Network planning and design,Steiner tree problem,Tree (data structure),Preprocessor,Mathematics,Special case
Journal
Volume
Issue
ISSN
7
1-2
Discrete Optimization
Citations 
PageRank 
References 
7
0.48
15
Authors
3
Name
Order
Citations
PageRank
Mohamed Haouari170655.24
Safa Bhar Layeb2262.25
Hanif D. Sherali33403318.40