Publication: A Lagrangian relaxation approach to large-scale flow interception problems
Institution Authors
Authors
Journal Title
Journal ISSN
Volume Title
Type
Article
Access
info:eu-repo/semantics/restrictedAccess
Publication Status
published
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.
Date
2009-10-16
Publisher
Elsevier
Description
Due to copyright restrictions, the access to the full text of this article is only available via subscription.