УДК 519.85
Яковлев Сергій Всеволодович, доктор фізико-математичних наук, професор Національного аерокосмічного університету ім. М.Є. Жуковського «Харківський авіаційний інститут»
Пічугіна Оксана Сергіївна, кандидат фізико-математичних наук, доцент Національного аерокосмічного університету ім. М.Є. Жуковського «Харківський авіаційний інститут»
Ярова Ольга Володимирівна, старший викладач Національного аерокосмічного університету ім. М.Є. Жуковського «Харківський авіаційний інститут»
pages 27–40
DOI: 10.1615/JAutomatInfScien.v51.i1.30
Виділено клас поліедрально-сферичних конфігурацій як вписаних в гіперсферу скінченних точкових конфігурацій. Запропоновано підходи до визначення параметрів конфігурацій. Розглянуто властивості задач оптимізації на поліедрально-сферичних конфігураціях, сформульовано теореми про існування опуклих продовжень для функцій і оцінку їх мінімумів. Результати конкретизовані для класу квадратичних функцій, заданих на переставних конфігураціях.
Ключові слова: дискретна оптимізація, конфігурація, поліедр, гіперсфера, опукле продовження, оцінка мінімуму.
1. Korte B., Vygen J. Combinatorial optimization: theory and algorithms. Heidelberg; New York : Springer, 2018. 698 p. https://doi.org/10.1007/978-3-662-56039-6 .
2. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: algorithms and complexity. Mineola : Dover Publications, 2013. 528 p.
3. Pardalos P.M., Du D-Z., Graham R.L. (Eds.) Handbook of combinatorial optimization. New York : Springer, 2013. 3409 p. https://doi.org/10.1007/978-1-4419-7997-1 .
4. Schrijver A. Combinatorial optimization: polyhedra and efficiency. Springer Science and Business Media, 2002. 2024 p.
5. Burkard R.E. Quadratic assignment problems. Handbook of combinatorial optimization . 2013. Vol. 5, N 1. P. 2741–2814. https://doi.org/10.1007/978-1-4419-7997-1_22 .
6. Sergienko I.V. , Shilo V.P. Modern approaches to solving complex discrete optimization problems. Journal of Automation and Information Sciences. 2016. Vol. 48, N 1. P. 15–24. https://doi.org/10.1615/JAutomatInfScien.v48.i1.30.
7. Sergienko I.V. , Hulianytskyi L.F. , Sirenko S.I. Classification of applied methods of combinatorialи optimization . Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 732–741. https://doi.org/10.1007/s10559-009-9134-0.
8. Згуровский М.З., Павлов А.А. Труднорешаемые задачи комбинаторной оптимизации в планировании и принятии решений. К. : Наук. думка, 2016. 115 с.
9. Semenova N.V., Kolechkina L.N., Nagornaya A.N. Solution and investigation of vector problems of combinatorial optimization on a set of polypermutations. Journal of Automation and Information Sciences. 2008. Vol. 40, N 6. P. 27 42. https://doi.org/10.1615/JAutomatInfScien.v40.i12.30 .
10. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems. Springer Optimization Methods and its Applications. 2017. Vol. 130. P. 239–250. https://doi.org/10.1007/978-3-319-68640-0_11.
11. Berge C. Principes de combinatoire. Paris : Dunod, 1968. 146 p.
12. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. К. : Наук. думка, 1986. 268 с.
13. Стоян Ю.Г., Ємець О.О. Теорія і методи евклідової комбінаторної оптимізації. К. : Ін-тсистемн. дослідж. освіти, 1993. 188 с.
14. Стоян Ю.Г., Яковлев С.В., Пичугина О.С. Евклидовы комбинаторные конфигурации.Харьков : Константа, 2017. 404 с.
15. Пичугина О.С., Яковлев С.В. Непрерывные функциональные представления в задачах дискретной оптимизации. Харьков : Золотая миля, 2018. 312 c.
16. Ferreira O.P., Iusem A.N., Németh S.Z. Concepts and techniques of optimization on the sphere. TOP. 2014. Vol. 22, N 3. Р. 1148–1170. https://doi.org/10.1007/s11750-014-0322-3 .
17. Gräf M., Hielscher R. Fast global optimization on the torus, the sphere, and the rotation group. SIAM J. Optim. 2015. Vol. 25, N 1. Р. 540–563. http://doi.org/10.1137/130950070 .
18. Yakovlev S.V. The theory of convex continuations of functions on vertices of convex polygons.
Computational Mathematics and Mathematical Physics. 1994. Vol. 34, N 7. P. 959–965. https://dl.acm.org/citation.cfm?id=196926 .
19. Yakovlev S. Convex extensions in combinatorial optimization and their applications. Springer Optimization Methods and its Applications. 2017. Vol. 130. P. 567–584. http://doi.org/10.1007/ 978-3-319-68640-0_27 .
20. Yakovlev S.V. Bounds on the minimum of convex functions on Euclidean combinatorial sets. Cybernetics. 1989. Vol. 25, N 3. P. 385–391. http://dx.doi.org/10.1007/BF01069996 .
21. Pichugina O.S., Yakovlev S.V. Continuous representations and functional extensions in combinatorial optimization. Cybernetics and Systems Analysis. 2016. Vol. 52, N 6. P. 921–930. http://doi.org/10.1007/s10559-016-9894-2 .
22. Pichugina O.S., Yakovlev S.V. Functional and analytic representations of the general permutations. Eastern-European Journal of Enterprise Technologies. 2016. Vol. 1, N 4. P. 27–38. http://doi.org/10.15587/1729-4061.2016.58550.
23. Yakovlev S.V., Grebennik I.V. Localization of solutions of some problems of nonlinear integer optimization. Cybernetics and Systems Analysis. 1993. Vol. 29, N 5. P. 727–734. https://doi.org/10.1007/BF01125802 .
24. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in .nR Cybernetics and Systems Analysis. 1991. Vol. 27, N 4. P. 562–567. http://dx.doi.org/10.1007/BF01130367 .
25. Yakovlev S.V., Pichugina O.S. Properties of combinatorial optimization problems over polyhedral-spherical sets. Cybernetics and Systems Analysis. 2018. Vol. 54, N 1. P. 385–391. https://doi.org/10.1007/s10559-018-0011-6 .
26. Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: theory and applications. In2017 IEEE First Ukraine Conference on Electrical and Computer Engineering (UKRCON). Proceedings, 2017. P. 1167–1175. https://doi.org/10.1109/UKRCON.2017.8100436 .
27. Schneider P., Eberly D.H. Geometric tools for computer graphics. Amsterdam : Morgan Kaufmann, 2002. 1056 p.
28. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация (комбинаторная теория многогранников). М. : Наука, 1981. 344 с.
29. Stoyan Y.G., Yakovlev S.V., Emets O.A., Valuiskaya O.A. Construction of convex continuations for functions defined on hypersphere. Cybernetics and Systems Analysis. 1998. Vol. 34, N 2. P. 176–184. https://doi.org/10.1007/BF02742066 .
30. Yakovlev S., Pichugina O., Yarovaya O. On polyhedral-spherical configurations: modelling andoptimization. In 2018 International Conference on Innovations in Engineering, Technology and Sciences (ICIETS). Proceedings, Karnataka, India, 2018. P. 100–105.
31. Yakovlev S., Pichugina O., Yarovaya O. On optimization problems on the polyhedral-spherical configurations with their properties. In 2018 IEEE First International Conference on System Analysis and Intelligent Computing (SAIC 2018). Proceedings, Kyiv, 2018. P. 94–100. http://dx.doi.org/10.1109/SAIC.2018.8516801.
32. Yakovlev S.V., Valuiskaya O.A. Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints. Ukrainian Mathematical Journal. 2001. Vol. 53, N 9. P. 1535–1545. https://doi.org/10.1023/A:1014374926840 .
33. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 716–726. https://doi.org/10.1007/s10559-018-0073-5 .
34. Yakovlev S.V. On some classes of spatial configurations of geometric objects and their formalization. Journal of Automation and Information Sciences. 2018. Vol. 50, N 5. P. 73–84. https://doi.org/10.1615/JAutomatInfScien.v50.i9.30 .
35. Yakovlev S.V. The method of artificial space dilation in problems of optimal packing of geometric objects. Cybernetics and Systems Analysis. 2017. Vol. 53, N 5. P. 725–731. https://doi.org/10.1007/s10559-017-9974-y.
36. Yakovlev S., Kartashov O. System analysis and classification of spatial configurations. In 2018 IEEE First International Conference on System Analysis and Intelligent Computing (SAIC 2018) Proceedings, Kyiv, 2018. P. 90–93. https://doi.org/10.1109/SAIC.2018.8516760 .
37. Combinatorial configurations in balance layout optimization problems. I.V. Grebennik, A.A. Kovalenko, T.E. Romanova, I.A. Urniaieva, S.B. Shekhovtsov. Cybernetics and Systems Analysis. 2018. Vol. 54, N 2. P. 221–231. https://doi.org/10.1007/s10559-018-0023-2 .
38. Chernov N., Stoyan Y., Romanova T. Mathematical model and efficient algorithms for object мpacking problem. Computational Geometry: Theory and Applications. 2010. Vol. 43, N 5. P. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003 .
39. Yakovlev S.V. On a class of problems on covering of a bounded set. Acta Mathematica Hungarica. 1989. Vol. 53, N 3. P. 253–262. https://doi.org/10.1007/BF01953365 .
40. Shekhotsov S.B., Yakovlev S.V. Formalization and solution of one class of covering problem in design of control and monitoring systems. Avtomatica I Telemekhanika. 1989. N 5. P. 160–168.
41. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distributed masses. Energomashinostroenie. 1982. N 2. P. 4–5. https://www.osti.gov/etdeweb/biblio/6490782 .
42. Pichugina O. Placement problems in chip design: modeling and optimization. In 2017 IEEE 4th International Scientific-Practical Conference Problems of Infocommunications Science and Technology. Proceedings, Kharkiv, 2017. P. 465–473. https://doi.org/10.1109/INFOCOMMST.2017.8246440 .
43. Farzad B., Pichugina O., Koliechkina L. Multi-layer community detection. In 2018 International Conference on Control, Artificial Intelligence, Robotics and Optimization (ICCAIRO) — Proceedings, Prague, 2018. P. 101–108.
44. Gerasin S.N., Shlyakhov V.V., Yakovlev S.V. Set coverings and tolerance relations. Cybernetics and Systems Analysis. 2008. Vol. 43, N 3. P. 333–340. https://doi.org/10.1007/s10559-008-9007-y .
45. Yakovlev S., Kartashov O., Yarovaya O. On class of genetic algorithms in optimization problems on combinatorial configuration. In 2018 IEEE XIІI International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT 2018). Proceedings,
Lviv, 2018. P. 374–377. https://doi.org/10.1109/STC-CSIT.2018.8526 .
46. Yakovlev S., Kartashov O., Pichugina O., Koliechkina L. The Genetic Algorithms in Optimization Problem on Combinatorial Configurations. In 2018 International Conference on Innovations in Engineering, Technology and Sciences (ICIETS). Proceedings, Karnataka, India, 2018. P. 106–111.