A network design problem which arises in the distribution
of a public utility provided by several competitive
suppliers is studied. The problem addressed is that of
determining minimum-cost (generalized) arc capacities
in order to accommodate any demand between given
source–sink pairs of nodes, where demands are assumed
to fall within predetermined ranges. Feasible
flows are initially considered as simply bounded by the
usual arc capacity constraints. Then, more general linear
constraints are introduced which may limit the weighted
sum of the flows on some subsets of arcs. An exact
cutting plane algorithm is presented for solving both of
the above cases and some computational results are
reported.
