OPTIMAL EXPANSION OF CAPACITATED TRANSSHIPMENT NETWORKS

In this paper, we address the problem of allocating a given budget to increase the capacities of arcs in a transshipment network to minimize the cost of flow in the network. The capacity expansion costs of arcs are assumed to be piecewise linear convex functions. We use propertie s of the optimum solution to convert this problem into a parametric ne twork flow problem. The concept of optimum basis structure is used whi ch allows us to consider piecewise linear convex functions without int roducing additional arcs. The resulting algorithm yields an optimum so lution of the capacity expansion problem for all budget levels less th an or equal to the given budget. For integer data, the algorithm perfo rms almost all computations in integers. Detailed computational result s are also presented.