Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint
dc.contributor.author | Haouari, Mohamed | |
dc.contributor.author | Layeb, S. B. | |
dc.contributor.author | Sherali, H. D. | |
dc.date.accessioned | 2012-05-30T12:52:20Z | |
dc.date.available | 2012-05-30T12:52:20Z | |
dc.date.issued | 2010-08-01 | |
dc.identifier.issn | 1571-0653 | |
dc.identifier.uri | http://hdl.handle.net/10679/184 | |
dc.identifier.uri | http://www.sciencedirect.com/science/article/pii/S1571065310000648 | |
dc.description | Due to copyright restrictions, the access to the full text of this article is only available via subscription. | |
dc.description.abstract | This 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.language.iso | eng | en_US |
dc.publisher | Elsevier | en_US |
dc.relation.ispartof | Electronic Notes in Discrete Mathematics | |
dc.rights | restrictedAccess | |
dc.title | Strength of three MIP formulations for the prize collecting steiner tree problem with a quota constraint | en_US |
dc.type | Conference paper | en_US |
dc.peerreviewed | yes | en_US |
dc.publicationstatus | published | en_US |
dc.contributor.department | Özyeğin University | |
dc.contributor.authorID | (ORCID 0000-0003-0767-8220 & YÖK ID ) Haouari, Mohamed | |
dc.contributor.ozuauthor | Haouari, Mohamed | |
dc.identifier.volume | 36 | |
dc.identifier.startpage | 495 | |
dc.identifier.endpage | 502 | |
dc.identifier.doi | 10.1016/j.endm.2010.05.063 | |
dc.subject.keywords | Steiner Tree | en_US |
dc.subject.keywords | MTZ subtour elimination constraints | en_US |
dc.subject.keywords | Reformulation-Linearization technique | en_US |
dc.subject.keywords | Mixed Integer Programming | en_US |
dc.identifier.scopus | SCOPUS:2-s2.0-77954904828 | |
dc.contributor.authorMale | 1 | |
dc.relation.publicationcategory | Conference Paper - International - Institutional Academic Staff |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
Share this page