To increase the reliability of a telephone network based on optic cables, a ring structure is used. An advantage of using rings is that the connection between telephone exchanges holds even if some cable is damaged. A ring is a cycle in the network graph. Different rings may contain the same nodes (telephone exchanges) as well as the same edges (optic cables) of the network graph. A flow can go from one ring to another only in a specially equipped telephone exchange common to both of them.

An increment of reliability can be achieved by flow planning. The total traffic for a specific pair of telephone stations may be transferred by diverse routes, so that a failure in ring equipment does not break the connection, and some fixed part of the total flow can be transferred anyway.

The problem solved for Israel National Telephone Company (Bezeq) by the Institute for Industrial Mathematics is as follows. Let a network graph and a traffic matrix be given, where is the amount of traffic to be transferred between telephone exchanges and . A ring system should be designed in and capacities of the rings should be chosen so that all required flows can be transferred only via the rings without any additional cable, so that the total amount of traffic transferred via a specific ring does not exceed the capacity of the ring.

Two main criteria are used for the estimation of a ring system. One is the cost of ring equipment: the higher the equipment cost, the greater the ring capacity. The other criterion is flexibility: the maximal ratio of flow and capacity for all rings.

The general problem of designing a ring system optimal subject to some criterion, with the other criterion as a constraint, is clearly hard. But the problem of flexibility minimization for a given ring structure (problem F) can be solved precisely in polynomial time. For the general problem a heuristic algorithm was developed which generates a ring structure, estimates it and then changes the structure according to the estimation. The estimation is performed by solving problem F. Additional constraints providing diverse routes may be included into problem F. The latter problem can be formulated as a linear programming problem with a very large number of variables (variables correspond to paths in a graph). An algorithm based on the decomposition method and the column generation technique was developed for the solution of this problem.

As the solution of the problem, the user gets a list of ring structures ordered by equipment cost. All the solutions in the list are Pareto optimal, feasible, and the traffic for each solution has minimal flexibility for the given ring structure. The user can choose the solution with suitable values of the criteria.

A computer system was developed for designing the required ring structure. The system allows the user to enter parameters of the network into dialog boxes, to construct a part of the solution or the whole solution manually, to compare several solutions for decision making. The system is used by Bezeq for designing ring structures in Jerusalem, Haifa and Ramat Hasharon.