| Abstract: | This thesis presents a multicommodity flow problem on a telephone network, consisting in allocating telephone lines from one switching center to another to physical routes represented by edges. The criterion is the minimum of the total investment cost, in which the cost of each edge is a step function. Representing each group of lines between two vertices as a flow gives a very large model; decomposing these flows along paths permits the use of generalized programming; defining the total cost from the lines themselves exhibits a solution method by approximation. Three heuristic methods are presented. Solving by successive approximations to the actual costs of the lines gives a good solution. Rerouting lines from one path to another presents several pathologies which can be corrected, and shows the possibility of improving the solution yielded by the approximation method. |
