Premium
Upper bounds for single‐source uncapacitated concave minimum‐cost network flow problems
Author(s) -
Fontes Dalila B. M. M.,
Hadjiconstantinou Eleni,
Christofides Nicos
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10076
Subject(s) - mathematical optimization , upper and lower bounds , heuristic , flow network , minimum cost flow problem , maximum flow problem , flow (mathematics) , mathematics , branch and bound , local search (optimization) , computer science , mathematical analysis , geometry
In this paper, we describe a heuristic algorithm based on local search for the Single‐Source Uncapacitated (SSU) concave Minimum‐Cost Network Flow Problem (MCNFP). We present a new technique for creating different and informed initial solutions to restart the local search, thereby improving the quality of the resulting feasible solutions (upper bounds). Computational results on different classes of test problems indicate the effectiveness of the proposed method in generating basic feasible solutions for the SSU concave MCNFP very near to a global optimum. A maximum upper bound percentage error of 0.07% is reported for all problem instances for which an optimal solution has been found by a branch‐and‐bound method. © 2003 Wiley Periodicals, Inc.