A new proximal decomposition algorithm for routing in telecommunication networks

Journal Article

  • Author(s): P. Mahey, A. Ouorou, L. LeBlanc, J. Chifflet
  • Article first published online: 07 Dec 1998
  • DOI: 10.1002/(SICI)1097-0037(199807)31:4<227::AID-NET3>3.0.CO;2-F
  • Read on Online Library
  • Subscribe to Journal


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. © 1998 John Wiley & Sons, Inc. Networks 31: 227–238, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.