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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2006

Autores

Dalila B.M.M. Fontes (Autor) FEP; Eleni Hadjiconstatinou (Autor) Outra; Nicos Christofides (Autor) Outra

Revista

Título: Journal of Global Optimization

Vol. 34 Nº 1

Páginas: 127-155

ISSN: 0925-5001

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 15 Citações

ISI Web of Science

Scopus - 17 Citações

Classificação Científica

FOS: Ciências sociais > Economia e gestão

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 29