Bibliographic Details
| Title: |
A Lagrangean heuristic for the capacitated concave minimum cost network flow problem. |
| Authors: |
Larsson, Torbjörn, Migdalas, Athanasios, Rönnqvist, Mikael |
| Source: |
European Journal of Operational Research. 10/13/1994, Vol. 78 Issue 1, p116-129. 14p. 1 Chart, 4 Graphs. |
| Subjects: |
Network analysis (Planning), Lagrange equations, Mathematical optimization |
| Abstract: |
We propose a heuristic solution technique for the capacitated concave minimum cost network flow problem based on a Lagrangean dualization of the problem. Despite its dual character the algorithm guarantees the generation of primal feasible solutions which are local optima and therefore candidates of being the global optimum. The Lagrangean dual is solved by a subgradient search procedure and provides a lower bound to the optimal value. The lower bound is, in general, stronger than the one obtained by a linear approximation of the original problem. It can be used as a judgement of the quality of the solution or in a branch and bound procedure. Computational results from randomly generated problems are presented. [ABSTRACT FROM AUTHOR] |
|
Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
