A new proximal decomposition algorithm for routing in telecommunication networks

We present a new and much more efficient implementation of the proximal decomposition algorithm for routing in congested telecommunication networks. The routing model that we analyze is a static one intended for use as a subproblem in a network design context. After describing our new implementation of the proximal decomposition algorithm and reviewing the flow deviation algorithm, we compare the solution times for (1) the original proximal decomposition algorithm, (2) our new implementation of the proximal decomposition algorithm, and (3) the flow deviation algorithm. We report extensive computational comparisons of solution times using actual and randomly generated networks. These results show that our new proximal decomposition algorithm is substantially faster than the earlier proximal decomposition algorithm in every case. Our new proximal decomposition is also faster than the flow deviation algorithm if the network is not too congested and a highly accurate solution is desired, such as one within 0.1% of optimality. For moderate accuracy requirements, such as 1.0% optimality, and for congested networks, the flow deviation algorithm is faster. More importantly, solutions that we obtained from the proximal decomposition algorithm always involve flow on only a small number of routes between source–destination pairs. The flow deviation algorithm, however, can produce solutions with flows on a very large number of different routes between individual source–destination pairs.