Date of this Version


Document Type

Journal Article

Publication Details

Pre Print

Sugden, S., Han, J., McMahon, G.,(2006) An exact algorithm for the constant and non-linear cost function problem in economic synthesis of networks.

© Copyright Stephen Sugden, Jun Han and Graham McMahon, 2006.


In this paper we introduce a branch and bound algorithm for finding a tree solution of the minimum cost network flow problem with constant arc cost. We consider different situations such as unit and non-unit traffic demand. The entire searching process is interpreted and the methods used in different situations to prune the search tree are emphasized respectively. Empirical results indicate the efficiency of these techniques. While no algorithm exists for a piecewise-constant cost function problem, we provide a model for transforming the problem to one with constant arc costs. After the transformation, the piecewise constant cost function problem can be solved by most existing algorithms for the linear cost function problem.



This document has been peer reviewed.