A Branch-and-Bound algorithm for concave Network Flow Problems

• Type: Article in International Scientific Journal
• Date: 2006

Authors

Dalila B.M.M. Fontes (Author) FEP; Eleni Hadjiconstatinou (Author) Other; Nicos Christofides (Author) Other

Journal

Title: Journal of Global Optimization

Vol. 34 No. 1

Pages: 127-155

ISSN: 0925-5001

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 15 Citations

ISI Web of Science

Scopus - 17 Citations

Scientific classification

FOS: Social sciences > Economics and Business

Other information

Authenticus ID: P-004-Q4C

DOI: 10.1007/s10898-005-1658-x

Abstract (EN): In this paper a Branch-and-Bound (BB) algorithm is developed to obtain an optimal solution to the single source uncapacitated minimum cost Network Flow Problem (NFP) with general concave costs. Concave NFPs are NP-Hard, even for the simplest version therefore, there is a scarcity of exact methods to address them in their full generality. The BB algorithm presented here can be used to solve optimally single source uncapacitated minimum cost NFPs with any kind of concave arc costs. The bounding is based on the computation of lower bounds derived from state space relaxations of a dynamic programming formulation. The relaxations, which are the subject of the paper (Fontes et al., 2005b) and also briefly discussed here, involve the use of non-injective mapping functions, which guarantee a reduction on the cardinality of the state space. Branching is performed by either fixing an arc as part of the final solution or by removing it from the final solution. Computational results are reported and compared to available alternative methods for addressing the same type of problems. It could be concluded that our BB algorithm has better performance and the results have also shown evidence that it has a sub-exponential time growth.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 29