A NEW PROXIMAL DECOMPOSITION ALGORITHM FOR ROUTING IN TELECOMMUNICATION NETWORKS

We present a new and much more efficient implementation of the proxima l decomposition algorithm for routing in congested telecommunication n etworks. The routing model that we analyze is a static one intended fo r use as a subproblem in a network design context. After describing ou r new implementation of the proximal decomposition algorithm and revie wing the flow deviation algorithm, we compare the solution times for ( 1) the original proximal decomposition algorithm, (2) our new implemen tation of the proximal decomposition algorithm, and (3) the flow devia tion algorithm. We report extensive computational comparisons of solut ion times using actual and randomly generated networks. These results show that our new proximal decomposition algorithm is substantially fa ster 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 so lution is desired, such as one within 0.1% of optimality. For moderate accuracy requirements, such as 1.0% optimality, and for congested net works, the flow deviation algorithm is faster. More importantly, solut ions that we obtained from the proximal decomposition algorithm always involve flow on only a small number of routes between source-destinat ion pairs. The flow deviation algorithm, however, can produce solution s with flows on a very large number of different routes between indivi dual source-destination pairs. (C) 1998 John Wiley & Sons, Inc. Networ ks 31: 227-238, 1998.