A Lagrangian relaxation approach to large-scale flow interception problems

Name: A Lagrangian relaxation approach to large-scale flow interception problems
Author: Gzara, F., Erkut, Erhan

İsim	A Lagrangian relaxation approach to large-scale flow interception problems
Yazar	Gzara, F., Erkut, Erhan
Basım Tarihi:	2009-10-16
Basım Yeri	- Elsevier
Konu	Flow interception problem, Lagrangian relaxation, Subgradient optimization, Cutting planes, Dual heuristic
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	0377-2217
Kayıt Numarası	21dd797d-5fe1-47c6-8c3c-311f43f4df85
Lokasyon	Business Administration
Tarih	2009-10-16
Notlar	Due to copyright restrictions, the access to the full text of this article is only available via subscription.
Örnek Metin	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

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

A Lagrangian relaxation approach to large-scale flow interception problems

Yazar Gzara, F., Erkut, Erhan

Basım Tarihi 2009-10-16

Basım Yeri - Elsevier

Konu Flow interception problem, Lagrangian relaxation, Subgradient optimization, Cutting planes, Dual heuristic

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 0377-2217

Kayıt Numarası 21dd797d-5fe1-47c6-8c3c-311f43f4df85

Lokasyon Business Administration

Tarih 2009-10-16

Notlar Due to copyright restrictions, the access to the full text of this article is only available via subscription.

Örnek Metin 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