Show simple item record

dc.contributor.authorHaouari, Mohamed
dc.contributor.authorLayeb, S. B.
dc.contributor.authorSherali, H. D.
dc.date.accessioned2012-05-30T10:40:32Z
dc.date.available2012-05-30T10:40:32Z
dc.date.issued2010
dc.identifier.issn1572-5286
dc.identifier.urihttp://hdl.handle.net/10679/181
dc.identifier.urihttp://www.sciencedirect.com/science/article/pii/S1572528610000022
dc.descriptionDue to copyright restrictions, the access to the full text of this article is only available via subscription.
dc.description.abstractThis 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.en_US
dc.description.sponsorshipNSF ; Fatimah Alnijris Research Chair for Advanced Manufacturing Technology
dc.language.isoengen_US
dc.publisherElsevieren_US
dc.relation.ispartofDiscrete Optimization
dc.rightsrestrictedAccess
dc.titleAlgorithmic expedients for the prize collecting Steiner tree problemen_US
dc.typeArticleen_US
dc.peerreviewedyesen_US
dc.publicationstatuspublisheden_US
dc.contributor.departmentÖzyeğin University
dc.contributor.ozuauthorHaouari, Mohamed
dc.identifier.volume7
dc.identifier.issue1-3
dc.identifier.startpage32
dc.identifier.endpage47
dc.identifier.wosWOS:000277911400004
dc.identifier.doi10.1016/j.disopt.2010.01.001
dc.subject.keywordsSteiner treeen_US
dc.subject.keywordsReduction techniquesen_US
dc.subject.keywordsWorst-case analysisen_US
dc.subject.keywordsValid inequalitiesen_US
dc.identifier.scopusSCOPUS:2-s2.0-77950521593
dc.contributor.authorMale1


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record


Share this page