Abstract.This paper describes the application of a dynamic programming approach to find minimum flow cost spanning trees on a network with general nonlinear arc costs. Thus, this problem is an extension of the Minimum Spanning Tree (MST) problem since we also consider flows that must be routed in order to satisfy user needs. In fact, the MST, usually, considers fixed arc costs and in our case the arc cost functions are nonlinear, having in addition to the fixed cost a flow dependent component. The arc cost functions involved may be of any type of form as long as they are separable and additive. This is a new problem, which is NP-Hard and a dynamic programming approach was developed to solve it exactly for small and medium size problems. We also report computational experiments on over 1200 problem instances taken from the OR-Library.

Received: July 24, 2007

AMS Subject Classification: 90C27, 90C35, 90C39

Key Words and Phrases: dynamic programming, network flows, optimal trees, general nonlinear arc costs

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 40
Issue: 3