A Lagrangean heuristic for the capacitated concave minimum cost network flow problem

A Lagrangean heuristic for the capacitated concave minimum cost network flow problem

0.00 Avg rating0 Votes
Article ID: iaor1998896
Country: Netherlands
Volume: 78
Issue: 1
Start Page Number: 116
End Page Number: 129
Publication Date: Oct 1994
Journal: European Journal of Operational Research
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.