A LAGRANGEAN HEURISTIC FOR THE CAPACITATED CONCAVE MINIMUM-COST NETWORK FLOW PROBLEM

Citation
T. Larsson et al., A LAGRANGEAN HEURISTIC FOR THE CAPACITATED CONCAVE MINIMUM-COST NETWORK FLOW PROBLEM, European journal of operational research, 78(1), 1994, pp. 116-129
Citations number
30
Categorie Soggetti
Management,"Operatione Research & Management Science
ISSN journal
03772217
Volume
78
Issue
1
Year of publication
1994
Pages
116 - 129
Database
ISI
SICI code
0377-2217(1994)78:1<116:ALHFTC>2.0.ZU;2-H
Abstract
We propose a heuristic solution technique for the capacitated concave minimum cost network flow problem based on a Langrangean dualization o f the problem. Despite its dual character the algorithm guarantees the generation of primal feasible solutions which are local optima and th erefore candidates of being the global optimum. The Langrangean dual i s solved by a subgradient search procedure and provides a lower bound to the optimal value. The lower bound is, in general, stronger than th e one obtained by a linear approximation of the original problem. It c an be used as a judgement of the quality of the solution or in a branc h and bound procedure. Computational results from randomly generated p roblems are presented.