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

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.