Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1015.90020
Mahey, P.; Ouorou, A.; LeBlanc, L.; Chifflet, J.
A new proximal decomposition algorithm for routing in telecommunication networks. (English)
[J] Networks 31, No.4, 227-238 (1998). ISSN 0028-3045; ISSN 1097-0037/e

Summary: 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.

MSC 2000:: *90B18 Communication networks
49M27 Decomposition methods

Keywords: decomposition algorithm; telecommunication networks

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]