Optimal Hop-Constrained Trees for Nonlinear Cost Flow Networks

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

Autores

Dalila B.M.M. Fontes (Autor) FEP

Revista

Título: INFOR: Information Systems and Operational Research

Vol. 48 Nº 1

Páginas: 13-21

ISSN: 0315-5986

Editora: Taylor & Francis

Indexação

ISI Web of Knowledge - 2 Citações

ISI Web of Science

Scopus - 2 Citações

Classificação Científica

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

CORDIS: Ciências Sociais > Economia > Estudos de gestão > Gestão industrial ; Ciências Físicas > Matemática > Matemática aplicada > Investigação operacional ; Ciências Sociais > Economia > Estudos de gestão > Gestão da produção

Outras Informações

ID Authenticus: P-003-9CT

DOI: 10.3138/infor.48.1.013

Abstract (EN): In this work we propose a new problem, that we have named hop-constrained minimum cost flow spanning tree problem, and develop an exact solution methodology. This problem is an extension of the well know NP-hard hop-constrained Minimum Spanning Tree problem (MST), since in addition to finding the arcs to be used we also must find the amount of flow that is to be routed through each arc. The hop-constrained MST has numerous practical applications in the design of communication networks. The hop constraints are usually used to guarantee a certain quality of service with respect to availability, reliability and lower delays, since they limit the number of arcs in each path from the central service provider. Including the flows, as we propose, allows for different levels of service requirements. A further extension is considered: the cost functions may have any type or form, may be neither convex nor concave, and need not to be differentiable or continuous. We develop a dynamic programming approach, which extends the scope of application of a previous work, to solve to optimality such problems. Computational experiments are performed using randomly generated test problems. Results showing the robustness of the method are reported.

Idioma: Inglês

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

Nº de páginas: 9