Optimal and suboptimal capacity allocation in communication networks

Gomory and Hu (Ref. 1) formulated the optimal allocation of capacities to the links of a communication networks as a problem in linear programming. The application of this formulation to the solution of problems of realistic size does, however, require an excessive amount of computation. In the present paper, a slightly different formulation is given. The resulting optimality conditions readily lend themselves to the construction of problems with known optimal solutions, thereby providing suitable examples for the assessment of the efficiencies of approximate methods. An approximate method that has been found highly efficient in many cases is illustrated by an example.