Author
Gzara, F., Erkut, Erhan
Publication Date
2009-10-16
Publication Place
-
Elsevier
Subject
Flow interception problem, Lagrangian relaxation, Subgradient optimization, Cutting planes, Dual heuristic
Type
Periodical
Language
English
Digital
Yes
Manuscript
No
Library
Özyeğin University
Library Asset ID
0377-2217
Record ID
21dd797d-5fe1-47c6-8c3c-311f43f4df85
Library Location
Business Administration
Date
2009-10-16
Notes
Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Sample Text
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.
DOI
10.1016/j.ejor.2008.08.024
Cilt
198
