Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
COMPLEXITY ANALYSIS OF OPTIMIZATION PROBLEMS
OF UTILITYCOMMUNICATIONS NETWORKS
DOI: 10.36724/2072-8735-2020-14-9-17-23
Gulzhigit Y. Toktoshov, Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia, tgi_tok@rambler.ru
Anastasiya N. Yurgenson, Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia, nastya@rav.sscc.ru
Denis A. Migov, Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia, mdinka@rav.sscc.ru
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.
Keywords: utility communications, graph, hypernet, NP- hard, metaheuristics.
References
1. Toktoshov G.Y, Yurgenson A.N. and Migov D.A. (2018). On a Problem of the Utility Network Design. OPTA-SCL 2018, (Springer), 8-14 July.2018. Vol. 2098. P. 385-395.
2. Noskov S.I., Ryazantsev A.I. (2019). Two-criteria transport problem. T-Comm, vol. 13, no.2, pр. 59-63. (in Russian)
3. Fedotov V.N., Aleksikov S.V. (2019). Research of productive technological motor transport during transportation of light oil products in urban conditions. T-Comm, vol. 13, no.2, pр. 64-68. (in Russian)
4. Stennikov V.A., Chemezov A.A. (2018). Application of trees search algorithm and Simulated annealing method for system- structural optimization of the heating networks. Software products and systems. №2 (31). P. 387-395. (in Russian)
5. Naumov I.V., Yamschikova I.V. (2015). Mathematical justification of the optimization model choice for the electrical network trace. Eurasian Union of Scientist. No.7 (16). P. 123-127. (inRussian)
6. Stepanov V.P. (2012). Routes optimization on the road network. Science and education. No. 5. P. 1-12. (in Russian)
7. Akimov S.V. (2005). Model of morphological set of identification level. Proceedings of educational institutions of communication. St. Petersburg, 2005. No. 172. P. 120-135. (in Russian)
8. Ankudinov G.I. (1986). Synthesis of the structure of complex objects. Logic-combinatorial approach. Leningrad: Publishing House of the Leningrad University. 260 р. (in Russian)
9. Kutergin A.V. (2012). Tensor methodology for finding the system’s optimal structure. Electronic scientific publication «Sustainable innovative development: design and management». No.2(15). Vol. 8. P. 74-106. (in Russian)
10. Odrin V.M. (1989). Method of morphological analysis of technical systems. Moscow: VNII-PI. 312 р. (in Russian)
11. Han L.Z., Zhang J.Q., Yang Y. (2014). Optimal placement of sensors for monitoring systems on suspension bridges using genetic algorithms. Applied Mechanics and Materials. Vol. 530. P. 320-331.
12. Wang K., Zhao H., Ding Y., Li T., Hou L., Sun F. (2015). Optimization of air pollutant monitoring stations with constraints using genetic algorithm. Journal of High Speed Networks. Vol. 21(2). P. 141-153.
13. Poulovassilis A., Levene M. (1994). A Nested-Graph Model for the Representation and Manipulation of Complex Objects. J. ACM Trans. Inf. Syst. Vol.12., P. 35-68.
14. Kurant M., Thiran P.(2006). Layered Complex Networks. J. Phys. Rev. Lett. Vol. 96. P.1-4.
15. Popkov V.K. (2011). On Modeling City Traffic Systems with Hypernetworks. Automation and Remote Control, 2011, 72(6). P. 179-189. (inRussian)
16. Zhumagulov B.T., Kalimoldaev M.N., Popkov V.K. and Toktoshov G.Y. (2013). Hypernet model and methods for optimizing design solutions for laying oil pipelines in difficult conditions. Т-Сomm. No.2. P. 36-40 (in Russian)
17. Monakhov O.G., Monakhov E.A. and Toktoshov G.Y. (2015). The differential evolution algorithm in the utility networks routes optimization problems. Science and education. Electronic magazine. No.09. P. 135-144 (in Russian)
18. Gary M., Johnson D. (1982). Computing machines and hard problems. Moscow. 416 p. (in Russian)
19. Jurgenson A.N., Migov D.A. (2019). On the complexity of the task of finding a minimum cost hypernet. Proceedings of the XV International Asian school-seminar «Optimization Problems of Complex Systems», Novosibirsk. 2019. P. 85-89 (in Russian)
20. Talbi El-G. Metaheuristics. From design to implementation. New Jersey:Wiley, 2009. p. 593.
21. Gordeev E.N., Tarastsov O.G. (1993). Steiner problem. Overview. Disc. Mat. Vol. 5, issue 2. P. 3-28. (in Russian)
22. Kononov A.V., Kononova P.A. (2014). Approximate algorithms for NP-hard problems. Novosibirsk. 117 p. (in Russian)
23. Popkov V.K., Toktoshov G.Y., Yurgenson A.N. (2012). One approach to the optimization engineering networks infrastructures. Bulletin of the SibSUTIS. No. 3. P. 11-28. (in Russian)
Information about authors:
Gulzhigit Y. Toktoshov, Cand. Sc., Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia
Anastasiya N. Yurgenson, Cand. Sc., Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia
Denis A. Migov, Cand. Sc., Institute of Computational Mathematics and Mathematical Geophysics of SB RAS, Novosibirsk, Russia