A Lagrangian relaxation approach to large-scale flow interception problems.(Report) Gzara, Fatma; Erkut, Erhan

User activity

Share to:
View the summary of this work
Gzara, Fatma ; Erkut, Erhan
Appears In
European Journal of Operational Research
Algorithms; Business, general; Business, international
Academic; Trade
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2008.08.024 Byline: Fatma Gzara (a), Erhan Erkut (b) Keywords: Flow interception problem; Lagrangian relaxation; Subgradient optimization; Cutting planes; Dual heuristic 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. Author Affiliation: (a) School of Administrative Studies, York University, 4700 Keele Street, Toronto, ON, Canada M3J 1P3 (b) Ozyegin University, Istanbul, Turkey Article History: Received 16 April 2007; Accepted 29 August 2008
Work ID

2 editions of this work

Find a specific edition
Thumbnail [View as table] [View as grid] Title, Author, Edition Date Language Format Libraries

User activity

e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this work

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this work

Add a comment

Show comments and reviews from Amazon users