Publication:
A Lagrangian relaxation approach to large-scale flow interception problems

Placeholder

Institution Authors

Research Projects

Journal Title

Journal ISSN

Volume Title

Type

article

Access

restrictedAccess

Publication Status

published

Journal Issue

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.

Keywords

Citation


Page Views

0

File Download

0