Optimal Hop-Constrained Trees for Nonlinear Cost Flow Networks

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

Authors

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

Journal

Title: INFOR: Information Systems and Operational Research

Vol. 48 No. 1

Pages: 13-21

ISSN: 0315-5986

Publisher: Taylor & Francis

Indexing

ISI Web of Knowledge - 2 Citations

ISI Web of Science

Scopus - 2 Citations

Scientific classification

FOS: Social sciences > Economics and Business

CORDIS: Social sciences > Economics > Management studies > Industrial management ; Physical sciences > Mathematics > Applied mathematics > Operations research ; Social sciences > Economics > Management studies > Production management

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 9