A Lagrangian relaxation approach to large-scale flow interception problems
dc.contributor.author | Gzara, F. | |
dc.contributor.author | Erkut, Erhan | |
dc.date.issued | 2009-10-16 | |
dc.identifier.issn | 0377-2217 | |
dc.identifier.uri | http://hdl.handle.net/10679/70 | |
dc.identifier.uri | http://www.sciencedirect.com/science/article/pii/S037722170800742X | |
dc.description | Due to copyright restrictions, the access to the full text of this article is only available via subscription. | |
dc.description.abstract | The paper presents a tight Lagrangian bound and an efficient dual heuristic for the flow interception problem. The proposed Lagrangian relaxation decomposes the problem into two subproblems that are easy to solve. Information from one of the subproblems is used within a dual heuristic to construct feasible solutions and is used to generate valid cuts that strengthen the relaxation. Both the heuristic and the relaxation are integrated into a cutting plane method where the Lagrangian bound is calculated using a subgradient algorithm. In the course of the algorithm, a valid cut is added and integrated efficiently in the second subproblem and is updated whenever the heuristic solution improves. The algorithm is tested on randomly generated test problems with up to 500 vertices, 12,483 paths, and 43 facilities. The algorithm finds a proven optimal solution in more than 75% of the cases, while the feasible solution is on average within 0.06% from the upper bound. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Elsevier | en_US |
dc.relation.ispartof | European Journal of Operational Research | |
dc.rights | restrictedAccess | |
dc.title | A Lagrangian relaxation approach to large-scale flow interception problems | en_US |
dc.type | Article | en_US |
dc.peerreviewed | yes | en_US |
dc.publicationstatus | published | en_US |
dc.contributor.department | Özyeğin University | |
dc.contributor.authorID | (ORCID 0000-0001-5806-0266 & YÖK ID 141720) Erkut, Erhan | |
dc.contributor.ozuauthor | Erkut, Erhan | |
dc.identifier.volume | 198 | |
dc.identifier.issue | 2 | |
dc.identifier.startpage | 405 | |
dc.identifier.endpage | 411 | |
dc.identifier.wos | WOS:000265802500006 | |
dc.identifier.doi | 10.1016/j.ejor.2008.08.024 | |
dc.subject.keywords | Flow interception problem | en_US |
dc.subject.keywords | Lagrangian relaxation | en_US |
dc.subject.keywords | Subgradient optimization | en_US |
dc.subject.keywords | Cutting planes | en_US |
dc.subject.keywords | Dual heuristic | en_US |
dc.identifier.scopus | SCOPUS:2-s2.0-63349094589 | |
dc.contributor.authorMale | 1 | |
dc.relation.publicationcategory | Article - International Refereed Journal - 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