Publication:
Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint

Simple item page
dc.contributor.authorHaouari, Mohamed
dc.contributor.authorLayeb, S. B.
dc.contributor.authorSherali, H. D.
dc.contributor.departmentIndustrial Engineering
dc.contributor.ozuauthorHAOUARI, Mohamed
dc.date.accessioned2012-05-30T12:52:20Z
dc.date.available2012-05-30T12:52:20Z
dc.date.issued2010-08-01
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 quota version of the Prize Collecting Steiner Tree Problem (PCSTP) on a graph as a generalization of the well-known Steiner tree problem. For this challenging network design problem that arises in telecommunication settings, we present three MIP formulations: (a) the first one is a compact Miller-Tucker-Zemlin (MTZ-) based formulation, (b) the second one is derived through lifting the MTZ constraints, and (c) the third one is based on the RLT technique. We report the results of extensive computational experiments on large PCSTP instances, having up to 2500 nodes using a general-purpose MIP solver.en_US
dc.identifier.doi10.1016/j.endm.2010.05.063
dc.identifier.endpage502
dc.identifier.issn1571-0653
dc.identifier.scopus2-s2.0-77954904828
dc.identifier.startpage495
dc.identifier.urihttp://hdl.handle.net/10679/184
dc.identifier.urihttps://doi.org/10.1016/j.endm.2010.05.063
dc.identifier.volume36
dc.language.isoengen_US
dc.peerreviewedyesen_US
dc.publicationstatuspublisheden_US
dc.publisherElsevieren_US
dc.relation.ispartofElectronic Notes in Discrete Mathematics
dc.relation.publicationcategoryInternational
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.subject.keywordsSteiner Treeen_US
dc.subject.keywordsMTZ subtour elimination constraintsen_US
dc.subject.keywordsReformulation-Linearization techniqueen_US
dc.subject.keywordsMixed Integer Programmingen_US
dc.titleStrength of three MIP formulations for the prize collecting steiner tree problem with a quota constrainten_US
dc.typeConference paperen_US
dspace.entity.typePublication
relation.isOrgUnitOfPublication5dd73c02-fd2d-43e0-9a23-71bab9ae0b6b
relation.isOrgUnitOfPublication.latestForDiscovery5dd73c02-fd2d-43e0-9a23-71bab9ae0b6b

Files

License bundle

Now showing 1 - 1 of 1
Placeholder
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Industrial Engineering