Optimal Synthesis of a Communication Net

This paper gives solutions to the problem of realizing a communication network at minimum cost. The network is composed of a set of nodes connected by a set of branches. Every branch has associated with it a capacity. The required amount of flow between every pair of nodes is specified. The unit costs of the branch capacities are given. The problem is to find the network and the branch capacities such that the total cost is minimum. The set of branch capacities and the set of terminal demands are shown to satisfy a set of linear inequalities. Linear programming is used to obtain the optimal solution. In the case of identical unit costs, several realizations are given which require fewer branches than previously reported.