UDC 519.85

THEORY AND METHODS OF EUCLIDIAN COMBINATORIAL OPTIMIZATION:
CURRENT STATE AND PROSPECTS

REFERENCES

1. Sergienko I.V., Shylo V.P. Discrete optimization problems: problems, solution methods, research [in Russian]. Kyiv.: Nauk. dumka, 2003. 261 p.


2. Sergienko I.V., Shylo V.P. Modern approaches to solving complex discrete optimization problems. Journal of Automation and Information Sciences. 2016. Vol. 48, N 1. P. 15–24.


3. Pardalos P.M., Du D-Z., Graham R.L. (Eds.) Handbook of combinatorial optimization. New York: Springer,. 2013. 3399 p.


4. Korte B., Vygen J. Combinatorial optimization: Theory and algorithms. Berlin; Heidelberg; New York: Springer, 2012. 660 p.


5. Papadimitriou C.H., Steiglitz K. Combinatorial optimization: Algorithms and complexity. Mineola (NY): Dover Publications, 2013. 528 p.


6. 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.


7. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems. Springer Optimization and its Applications. 2017. Vol. 130. P. 239–250.


8. Zgurovsky M.Z., Pavlov A.A. Intractable problems of combinatorial optimization in planning and decision making [in Russian]. Kiev: Nauk. dumka, 2016. 716 p.


9. Stoyan Yu.G. Some properties of special combinatorial sets. Kharkov: Inst. Probl. Engineering Academy of Sciences of the Ukrainian SSR, 1980. 22 p. (Preprint USSR Academy of Sciences, Inst. mechanical engineering; N 85).


10. Stoyan Yu.G. On a mapping of combinatorial sets into a Euclidean space. Kharkov: Inst. Probl. Engineering Academy of Sciences of the Ukrainian SSR, 1982. 33 p. (Preprint USSR Academy of Sciences, Inst. mechanical engineering; N 173).


11. Stoyan Yu.G., Yakovlev S.V. Mathematical models and optimization methods of geometric design [in Russian]. Kiev: Nauk. dumka, 1986. 268 p.


12. Berge C. Principes de combinatoire. Paris: Dunod, 1968. 146 p.


13. Sachkov V.N. Combinatorial methods of discrete mathematics [in Russian]. Moscow: Nauka, 1975. 319 p.


14. Stoyan Yu.G., Yakovlev S.V., Pichugina O.S. Euclidean combinatorial configurations [in Russian]. Kharkov: Constanta, 2017. 404 p.


15. Stoyan Yu.G., Emets O.O. Euclidean combinatorial optimization theory and methods [in Ukrainian]. Kiev: In-t system. dosl_dzh. osvity, 1993. 188 p.


16. Emets O.A., Barbolina T.N. Combinatorial optimization on placements [in Russian]. Kiev: Nauk. dumka, 2008. 159 p.


17. Emelichev V.A., Kovalev M.M., Kravtsov M.K. Polyhedra, graphs, optimization (combinatorial theory of polyhedra) [in Russian]. Moscow: Nauka, 1981. 344 p.


18. Donets G.P., Kolechkina L.M. Extremal problems on combinatorial configurations [in Ukrainian]. Poltava: PUET, 2011. 328 p.


19. Pichugina O., Brus A. Computer study of combinatorial sets and polytopes: Classification. Application in optimization and theory of geometric graphs. Saarbriicken: LAP LAMBERT Acad. Publ., 2014. 144 p.


20. Stoyan Yu.G., Grebennik I.V. Composite images of combinatorial sets and some of their properties. Prob. mechanical engineering. 2005. Vol. 8, N 3. P. 56–62.


21. Grebennik I.V. The combinatorial set of permutations of tuples and its properties. Radio Electronics Informatics. Control. 2005. N 1. P. 92–98.


22. Stoyan Yu.G., Grebennik I.V. Description of classes of combinatorial configurations based on mappings. Doc. NAS of Ukraine. 2008. N 10. P. 28–31.


23. Yemets O.A., Yemets A.O., Polyakov I.M. Criterion of an edge of a general polyhedron of arrangements. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 796–805.


24. Yemets O.A., Yemets A.O., Polyakov I.M. Optimization on arrangements: The simplex form of polyhedron of arrangements. Journal of Automation and Information Sciences. 2017. Vol. 49, N 12. P. 14–28.


25. Aardal K., Hoesel S. Polyhedral techniques in combinatorial optimization. I: Computations. Statistica Neerlandica. 1996. N 15. P. 3–26.


26. Aardal K., Hoesel S. Polyhedral techniques in combinatorial optimization. II: Theory. Statistica Neerlandica. 1999. N 2. P. 131–177.


27. Pichugina O.S., Yakovlev S.V. Continuous functional representations in discrete optimization problems [in Russian]. Kharkov: Zolotaya milya, 2018. 312 p.


28. 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.


29. Pichugina O., Yakovlev S. Convex extensions and continuous functional representations in optimization, with their applications. J. Coupled Syst. Multiscale Dyn. 2016. Vol. 4, N 2. P. 129–152.


30. 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.


31. Pichugina O., Yakovlev S. Continuous approaches to the unconstrained binary quadratic problems. Mathematical and Computational Approaches in Advancing Modern Science and Engineering. Edited Belair J., Frigaard I., Kunze H. Cham: Springer, Switzerland, 2016. P. 689–700.


32. Pichugina O.S., Yakovlev S.V. Continuous representation techniques in combinatorial optimization. IOSR Journal of Mathematics. 2017. Vol. 13, N 2, Ver. V. P. 12–25.


33. Pichugina O.S., Yakovlev S.V. Euclidean combinatorial configurations: continuous representations and convex extensions. Advances in Intelligent Systems and Computing. 2019. Vol. 1020. P. 65–80.


34. Pichugina O., Yakovlev S. Euclidean combinatorial configurations: Typology and applications. In: 2019 IEEE First Ukraine Conference on Electrical and Computer Engineering (July 2–6, 2019, Lviv). Lviv, 2019. P. 1065–1070.


35. Yakovlev S.V. The theory of convex continuations of functions on vertices of convex polyhedral. Comp. Math. and Math. Phys. 1994. Vol. 34. P. 1112–1119.


36. Yakovlev S. Convex extensions in combinatorial optimization and their applications. Springer Optimization and Its Applications. 2017. Vol. 130. P. 567–584.


37. Pogorelov A.V. External geometry of convex surfaces [in Russian]. Moscow: Nauka, 1969. 760 p.


38. Stoyan Yu.G., Yakovlev S.V., Parshin O.V. Optimization of quadratic functions on the set of permutations mapped to Rn. Doc. USSR Academy of Sciences. Ser. А. 1989. N 5. P. 73–78.


39. Stoyan Y.G., Yakovlev S.V., Parshin O.V. Quadratic optimization on combinatorial sets in . Cybernetics and Systems Analysis. 1991. Vol. 27, N 4. P. 562–567.


40. 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. 99–109.


41. Pichugina O., Yakovlev S. Optimization on polyhedral-spherical sets: Theory and applications. In: 2017 IEEE First Ukraine Conference on Electrical and Computer Engeneering (May 29–June 2, Kyiv). Kyiv, 2017. P. 1167–1175.


42. 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. (October 8–12, 2018, Kyiv). Kyiv, 2018. P. 94–100.


43. Yakovlev S., Pichugina O., Yarovaya O. Polyhedral-spherical configurations in discrete optimization problems. Journal of Automation and Information Sciences. 2019. Vol. 51, N 1. P. 26–40.


44. Stoyan Yu.G., Yakovlev S.V., Emets O.A., Valuyskaya O.A. On the existence of a convex continuation of functions defined on the hypersphere. Doc. NAS of Ukraine. 1998. N 2. P. 128–133.


45. Stoyan Yu.G., Yakovlev S.V., Yemets O.A., Valuyskaya O.A. Construction of convex continuations for functions defined on hypersphere. Cybernetics and System Analysis. 1998. Vol. 34, N 2. P. 27–36.


46. Stoyan Yu., Grebennik I., Kalashnikov V., Lytvynenko O. Enumeration and generation of permutations with a partially fixed order of elements. International Journal of Combinatorial Optimization Problems and Informatics. 2017. Vol. 8, N 1. P. 19–30.


47. Pichugina O., Kartashov O. Signed permutation polytope packing in VLSI design. In: 15th International Conference on the Experience of Designing and Application of CAD Systems (February 26–March 2, 2019, Polyana, Ukraine). Polyana, 2019. P. 50–55.


48. Pichugina O.S., Yakovlev S.V. Convex extensions for the class of quadratic problems on permutation matrices. Komp'yuternaya matematika. 2016. Iss. 1. P. 143–154.


49. Grebennik I.V. Description and generation of permutations containing cycles. Cybernetics and Systems Analysis. 2010. Vol. 46, N 6. P. 945–952.


50. Grebennik I.V., Lytvynenko O.S. Generation of combinatorial sets possessing special characteristics. Cybernetics and Systems Analysis. 2012. Vol. 48, N 6. P. 890–898.


51. Stoyan Yu.G., Yakovlev S.V. Construction of convex and concave functions on a permutable polyhedron. Doc. USSR Academy of Sciences. 1988. N 5. P. 68–70.


52. Yakovlev S.V. Bounds on the minimum of convex functions on Euclidean combinatorial sets. Cybernetics and Systems Analysis. 1989. Vol. 25, N 3. P. 385–391.


53. Yakovlev S.V. The theory of convex continuations in combinatorial optimization problems. Doc. NAS of Ukraine. 2017. N 8. P. 20–26.


54. Valuiskaya O.A., Yemets O.А., Romanova N.G. Stoyan–Yakovlev’s modified method applied to convex continuation of polynomials defined on polypermutations. Computational Mathematics and Mathematical Physics. 2002. Vol. 42, N 4. P. 591–596.


55. Yakovlev S., Pichugina O. On constrained optimization of polynomials on permutation set. In: Proceedings of the Second International Workshop on Computer Modeling and Intelligent Systems (April 15–19, 2019, Zaporizhzhia). Zaporizhzhia, 2019. P. 570–580.


56. Yakovlev S.V., Grebennik I.V. On some classes of optimization problems on combinatorial sets of allocations. Izv. vuzov. Ser. Mat. 1991. N 11. P. 74–86.


57. Pichugina O.O. Algorithm for constructing convex continuation on poly permutations and its scope. Problems of Computer Intellectualization. Kyiv (Ukraine)–Sofia (Bulgaria), 2012. P. 125–132.


58. Pichugina O., Yakovlev S. Quadratic optimization models and convex extensions on permutation matrix set. In: Shakhovska N. and Medykovskyy M.O. (Eds.) Advances in Intelligent Systems and Computing IV. Cham: Springer Nature, Switzerland, 2019. P. 231–246.


59. 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. 419–426.


60. Land A.H., Doig A.G. An automatic method of solving discrete programming problems. Econometrica. 1960. Vol. 28, N 3. P. 497–520.


61. Mikhalevich V.S. Sequential optimization algorithms and their application. Kibernetika. 1965. N 1. P. 45–56; N 2. P. 85–88.


62. Sergienko I.V., Iemets O.A., Chernenko O.A. Solving the conditional optimization problem for a fractional linear objective function on a set of arrangements by the branch and bound method. Cybernetics and Systems Analysis. 2012. Vol. 48, N 6. P. 832–836.


63. Iemets O.A., Yemets A.O.The solution of a minimization problem of the weighted length of a connecting grid by branch and bound method. Journal of Automation and Information Sciences. 2012. Vol. 44, N 7. P. 22–33.


64. Iemets O.A., Parfionova T.A. Transportation problems on permutations: properties of estimates in the branch and bound method. Cybernetics and Systems Analysis. 2014. Vol. 46, N 6. P. 953–959.


65. Yakovlev S.V., Parshin O.V. Approximate optimization methods at the vertices of a permutation polyhedron. Vestn. Kharkiv. un-ta. Dynamic systems. 1989. Iss. 334. P. 198–206.


66. Pichugina O.S., Yakovlev S.V. Global optimization methods on a permutation polyhedron in combinatorial problems on vertex-spaced sets. Mathematical and computer modeling. Ser. Phys.-mat. Sciences. 2017. N 15. P. 258–264.


67. Pichugina O.S., Yakovlev S.V. Methods of penalty functions for solving optimization problems on polyhedral-spherical sets. Radioelektronika i informatika. 2016. N 1. P. 18–26.


68. Stetsyuk P.I. Shor’s r-algorithms: Theory and practice. Springer Optimization and its Applications. 2017. Vol. 130. P. 239–250.


69. Stetsyuk P.I. Theory and software implementations of Shor’s -algorithms. Cybernetics and Systems Analysis. 2017. Vol. 53, N 5. P. 692–703.


70. Stoyan Yu.G., Yakovlev S.V. Properties of convex functions on a permutation polyhedron. Doc. USSR Academy of Sciences. Ser. А. 1988. N 3. P. 238–240.


71. 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.


72. Hulianytskyi L.F., Mulesa O.Y. Applied combinatorial optimization methods [in Ukrainian]. Kyiv: Kyiv University, 2016. 142 p.


73. Kozin I.V. Evolutionary models in discrete optimization problems [in Russian]. Zaporozhye: Zaporizhia. nat. un, 2019. 204 p.


74. 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 (September 11–14, 2018, Lviv). Lviv, 2018. P. 374–377.


75. Yakovlev S., Kartashov O., Pichugina O. Optimization on combinatorial configurations using genetic algorithms. In: CEUR Workshop Proceedings. 2019. Vol. 2353. P. 28–40.


76. Yakovlev S., Kartashov O., Pichugina O., Korobchynskyi K. Genetic algorithms for solving combinatorial mass balancing problem. In: 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering. (July 2–6, 2019, Lviv). Lviv, 2019. P. 1061–1064.


77. Yemets O.A., Yemets Y.M. Cutting in linear partially combinatorial problems of Euclidean combinatorial optimization. Dop. NAS of Ukraine. 2000. N 9. P. 105–109.


78. Yemets O.A., Yemets Y.M. A modification of the method of combinatorial truncation in optimization problems over vertex-located sets. Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 785–791.


79. Yemets O.A., Yemets Y.M., Chilikina T.V. Combinatorial cutting while solving optimization nonlinear conditional problems of the vertex located sets. Journal of Automation and Information Sciences. 2010. Vol. 42, N 5. P. 21–29.


80. Iemets O.O., Yemets E.M., Olhovskiy D.M. The method of cutting the vertices of permutation polyhedron graph to solve linear conditional optimization problems on permutations. Cybernetics and Systems Analysis. 2014. Vol. 50, N 4. P. 613–619.


81. Donets G.A., Kolechkina L.N. On an approach to solving the combinatorial optimization problem on graphs. Upr. sist. maš. 2009. N 4. P. 36–42.


82. Donec G.A., Kolechkina L.M. Construction of hamiltonian paths in graphs of permutation polyhedra. Cybernetics and Systems Analysis. 2016. Vol. 46, N 1. P. 7–13.


83. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 716–726.


84. 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 9. P. 38–50.


85. Stoyan Yu., Romanova T. Mathematical models of placement optimisation: two- and three-dimensional problems and applications. Modeling and Optimization in Space Engineering. New York: Springer, 2013. Vol. 73. P. 363–388.


86. Grebennik I.V., Kovalenko A.A., Romanova T.E., Urniaieva I.A., Shekhovtsov S.B. Combinatorial configurations in balance layout optimization problems. Cybernetics and Systems Analysis. 2018. Vol. 54, N 2. P. 221–231.


87. Stoyan Y., Pankratov A., Romanova T., Fasano G., Pinter J.D. Optimized packings in space engineering applications: Part I. Modeling and Optimization in Space Engineering. Springer Optimization and Its Applications. 2019. Vol 144. P. 395–437.


88. Stoyan Y., Grebennik I., Romanova T., Kovalenko A. Optimized packings in space engineering applications: Part II. Modeling and Optimization in Space Engineering. Springer Optimization and Its Applications. 2019. Vol 144. P. 439–457.


89. Yakovlev S.V. Configuration spaces of geometric objects with their applications in packing, layout and covering problems. Advances in Intelligent Systems and Computing. 2019. Vol. 1020. P. 122–132.


90. Kiseleva E.M., Prytomanova O.M., Zhuravel S.V. Algorithm for solving a continuous problem of optimal partitioning with neurolinguistic identification of functions in target functional. Journal of Automation and Information Science. 2018. Vol. 50, N 3. P. 1–20.


91. Kiseleva Е.М., Kadochnikova Y.E. Solving a continuous single-product problem of optimal partitioning with additional conditions. Journal of Automation and Information Science. 2009. Vol. 41, N 7. P. 48–63.


92. Stoyan Yu.G., Semkin V.V., Chugay A.M. Optimization of 3D objects layout into a multiply connected domain with account for shortest distances. Cybernetics and Systems Analysis. 2014. Vol. 50, N 3. P. 374–385.


93. Stoyan Y., Romanova T., Pankratov A., Kovalenko A., Stetsyuk P. Balance layout problems: Mathematical modeling and nonlinear optimization. Springer Optimization and Its Applications. 2016. Vol. 114. P. 369–400.


94. Stoyan Yu.G., Sokolovskii V.Z., Yakovlev S.V. Method of balancing rotating discretely distributed masses. Energomashinostroenie. 1982. N 2. P. 4, 5.


95. Pichugina O. Placement problems in chip design: Modeling and optimization. In: 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (October 10–13, 2017, Kharkiv). Kharkiv, 2017. P. 465–473.


96. Gritsik V.V., Shevchenko A.I., Kiselev O.M., Yakovlev S.V., Bidiuk P.I., Gil M.I., Krak Yu.V., Kulyas A.I., Romanova T.E., Stetsyuk P.I. Mathematical optimization methods and intelligent computer technologies for modeling complex processes and systems taking into account spatial shapes of objects [in Ukrainian]. Donetsk: Nauka i osvita, 2011. 480 p.


97. Yakovlev S.V. On the combinatorial structure of problems of optimal placement of geometric objects. Doc. NAS of Ukraine. 2017. N 9. P. 63–68.


98. Yakovlev S.V. The method of artificial dilation in problems of optimal packing of geometric objects. Cybernetics and Systems Analysis. 2017. Vol. 53, N 5. P. 725–731.


99. Hulianytskyi L.F., Riasna I.I. Automatic classification method based on a fuzzy similarity relation. Cybernetics and Systems Analysis. 2016. Vol. 52, N 1. P. 30–37.


100. Gulyanitsky L.F., Ryasna I.I. Before formalizing combinatorial optimization problems on fuzzy sets. Teoriya optymalʹnykh rishenʹ. 2016. N 1. P. 17–25.


101. Grebennik I.V. Interval models of combinatorial optimization of quasilinear functions in space. Doc. NAS of Ukraine. 2004. N 9. P. 60–64.


102. Grebennik I.V., Romanova T.E. The mapping of interval combinatorial sets into Euclidean space. Probl. mashinostroyeniya. 2002. Vol. 5, N 2. P. 87–91.


103. Yemets O.O., Iemets O.O. Solving combinatorial optimization problems on fuzzy sets. Poltava: PUET, 2011. 239 p.


104. Yemets O.A., Roskladka A.A. Combinatorial optimization under uncertainty. Cybernetics and Systems Analysis. 2008. Vol. 44, N 5. P. 655–663.


105. Romanova T.E., Evseeva L.G., Stoyan Yu.G. Combinatorial optimization problem of placing rectangles taking into account the errors of the source data. Doc. NAS of Ukraine. 1997. N 7. P. 56–60.


106. Stoyan Yu.G., Romanova T.E. Account of errors in optimization placement problem. Probl. mashinostroyeniya. 1998. Vol. 1, N 2. З. 31–41.


107. Grebennik I.V., Romanova T.E. Accounting for errors in the construction of mathematical models of optimization combinatorial problems. Avtomatizirovannyye Sistemy Upravleniya i Pribory Avtomatiki. 2002. Iss. 119. P. 64–69.


108. Kiseleva E., Hart L., Prytomanova O., Kuzenkov A. An algorithm to construct generalized Voronoi diagrams with fuzzy parameters based on the theory of optimal partitioning and neuro-fuzzy technologies. In: 8th International Conference on Mathematics, Information Technologies, Education (March 23–25, 2019, Xi’an, China). Xi’an, 2019. Р. 148–162.


109. Mashtalir V.P., Yakovlev S.V. Point-set methods of clusterization of standard information. Cybernetics and Systems Analysis. 2001. Vol. 37, N 3. Р. 295–307.


110. 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.


111. Mashtalir V.P., Shlyakhov V.V., Yakovlev S.V. Group structures on quotient sets in classification problems. Cybernetics and Systems Analysis. 2014. Vol. 50, N 4. P. 507–518.


112. Semenova N.V., Kolechkina L.M. Vector discrete optimization problems on combinatorial sets: research and solution methods [in Ukrainian]. Kiev: Nauk. Dumka, 2009. 266 p.


113. Emelichev V.A., Kotov V.M., Kuzmin K.G., Semenova N.V., Lebedeva T.T., Sergienko T.I. Stability and effective algorithms for solving multiobjective discrete optimization problems with incomplete information. Journal of Automation and Information Sciences. 2014. Vol. 46, N 2. P. 27–41.


114. Lebedeva T.T., Semenova N.V., Sergienko T.I Qualitative characteristics of the stability vector discrete optimization problems with different optimality principles. Cybernetics and Systems Analysis. 2014. Vol. 50, N 2. P. 228–233.


115. Sergienko I.V., Lebedeva T.T., Semenova N.V. Existence of solutions in vector optimization problems. Cybernetics and Systems Analysis. 2000. Vol. 36, N 6. P. 823–828.


116. Semenova N.V., Kolechkina L.N., Nagirna A.N. An approach to solving discrete vector optimization problems over a combinatorial set of permutations. Cybernetics and Systems Analysis. 2008. Vol. 44, N 3. P. 441–451.


117. Semenova N.V., Kolechkina L.N., Nagornaya A.N. On approach to solving vector problems with fractionally linear functions of the criteria on the combinatorial set of arrangements. Journal of Automation and Information Sciences. 2010. Vol. 42, N 2. P. 67–80.


118. Sergienko I.V., Semenova N.V., Semenov V.V. Bilevel optimization problems of distribution of interbudget transfers within given limitations. Cybernetics and Systems Analysis. 2019. Vol. 55, N 6. P. 730–740.


119. Yakovlev S.V. Formalizing spatial configuration optimization problems with the use of a special function class. Cybernetics and Systems Analysis. 2019. Vol. 55, N 4. P. 581–589.