CONCAVE COST MINIMIZATION ON NETWORKS

The paper deals with the problem of finding a minimum cost multicommodity flow on an uncapacitated network with concave link costs. Problems of this type are the optimal design of a network in the presence of scale economies and the telpack problem. Two different definitions of local optimality are given and compared both from the point of view of the computational complexity and from the point of view of the goodness of the solution they may provide. A vertex following algorithm to find a local optimum is proposed. The computational complexity of each iteration of the algorithm is O(n3), where n is the number of nodes of the network, and is independent of the differentiability of the objective function. Experimental results obtained from a set of test problems of size ranging from 11 nodes and 23 arcs to 48 nodes and 174 arcs, with number of commodities up to 5, are given. © 1979.