On a Decomposition Method for Designing Communication Networks

Abstract. This paper presents a communication network design algorithm for finding a guaranteed transportation plan of a given volume under uncertain factors. The volumes of production and the capacities of communication lines are expressed as linear functions of invested resources. The well-known Dantzig–Wolfe decomposition algorithm is applied to solve the dual problem due to its stepped block structure. In view of their specifics, the linear problems arising in iterations are solved using effective network and graph theory methods: the maximum flow, the minimum cutset in the network, the connectivity components, and the minimum spanning trees of the graphs are found. The existing algorithms for these problems have the complexity estimates О(mn2), О(n2m), and O(n + m), where n is the number of graph vertices and m is the number of edges.

Keywords: supply and demand problem, communication networks, linear design, decomposition methods, maximum flow, minimum cutset, minimum spanning tree.

Cite this paper