COMPLEXITY ANALYSIS OF OPTIMIZATION PROBLEMS OF UTILITYCOMMUNICATIONS NETWORKS
Gulzhigit Toktoshov, Anastasiya Yurgenson, Denis A. Migov
Abstract
The problems of optimizing engineering communications networks according to various criteria, such as, minimum total construction costs, reliability, and compatibility are considered. A new technique for modeling utility networks based on the hypernet model, which allows one to take into account the nesting of one structure in another and the interdependence of indicators of the elements of these structures, is proposed. This approach makes the considered in these paper optimizations problems universal, and allows to take into account the interaction of the designed types of networks with each other. In addition, by combining the problems presented in this paper, various variations of optimization problems can be obtained. In this case, multicriterial tasks are stated, such as design networks of minimum cost, taking into account their reliability; design networks of minimum cost, taking into account their compatibility and reliability, and others. Note that all these problems are NP-hard, for the solution of which do not exist polynomial exacts algorithms. In particular, it was shown that the optimization problem in the simplest hypernet formulation is NP-hard. The possibility of applying accurate and approximate methods for solving them, and assessing the accuracy of these methods, were examined.