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.