The theory of convex extensions in combinatorial optimization problems
DOI:
https://doi.org/10.15407/dopovidi2017.08.020Keywords:
combinatorial optimization, combinatorial polyhedron, convex extension, vertex located setAbstract
The results of the theory of convex extensions for vertex located and polyhedral-spherical sets are summarized. In view of the theorems of existence of convex differentiable extensions, the problem is equivalent to a discrete optimization problem of convex functions under convex functional constraints. The convex nonlinear relaxation problem is considered.
Downloads
References
Sergienko, I. V. & Shilo, V. P. (2003). Discrete optimization problem. Kiev: Naukova Dumka (in Russian).
Korte, B. & Vygen, J. (2002). Combinatorial Optimization: Theory and Algorithms. Heidelberg etc.: Springer. https://doi.org/10.1007/978-3-662-21711-5
Hulianytskyi, L. F. & Mulesa, O. Y. (2016). Applied methods of combinatorial optimization. Kiev: Kyiv University Press (in Ukrainian).
Stoyan, Y. G. & Yakovlev, S. V. (1986). Mathematical models and optimization methods of geometric design. Kiev: Naukova Dumka (in Russian).
Yakovlev, S. V. (1994). Theory of convex extensions of functions on the vertices of a convex polyhedron. J. Comp. Math. and Math. Phys. 34 (7), pp. 1112-1119 (in Russian).
Sergienko, I. V., Hulianytskyi, L. F. & Sirenko, S. I. (2009). Classification of applied methods of combinatorial optimization. Cybernetics and system analysis, No. 5, pp. 71-83 (in Russian). https://doi.org/10.1007/s10559-009-9134-0
Hulianytskyi, L. F. & Sergienko, I. V. (2007). Metaheuristic method of deformed polyhedron in combinatorial optimization. Cybernetics and system analysis, No. 6, pp. 70-79 (in Russian).
Yakovlev, S. V., Gil, N. &. Komyak, V. M., et. al. (1995). Elements of the theory of geometric design. Kiev: Naukova Dumka (in Russian).
Grichik, V. V., Kiselyova, O. M. & Yakovlev, S. V., et. al. (2012). Mathematical methods of optimization and intelligent computer technologies for modeling complex systems with consideration of spatial shapes of objects. Donetsk: Nauka and Osvita (in Ukrainian).
Emelichev, V. A., Kovalev, M. M. & Kravtsov, M. K. (1981). Polytopes, graphs, optimization (combinatorial theory of polytopes). Moscow: Nauka (in Russian).
Pichugina, O. S. & Yakovlev, S. V. (2016). On continuous representations and functional continuations in combinatorial optimization. Cybernetics and system analysis. 52, No. 6, pp. 102-113 (in Russian). http://link.springer.com/article/10.1007/s10559-016-9894-2 https://doi.org/10.1007/s10559-016-9894-2
Pichugina, O. & Yakovlev, S. (2016). Convex extensions and continuous functional representations in optimization with their applications. J. Coupled Syst. Multiscale Dyn., 4 (2), pp. 129-152 (in Russian). http://link.springer.com/article/10.1007/s10559-016-9894-2
http://www.ingentaconnect.com/contentone/asp/jcsmd/2016/00000004/0000000.
Stoyan, Yu. G. & Yakovlev, S. V. (1988). Construction of convex and concave functions on the permutation polyhedron. Doklady Academy of Science USSR, Ser. A. No. 5, pp. 66-68 (in Russian).
Stoyan, Yu. G., Yakovlev, S. V., Yemets, O. A. & Valuyskaya, O. A. (1995). Construction of convex continuations for functions defined on hypersphere. Cybernetics and system analysis. No. 2, pp. 27-36 (in Russian).
Yakovlev, S. V. (1989). Estimates of the minimum of convex functions on Euclidean combinatorial sets. Cybernetics. No. 3, pp. 89-97 (in Russian).
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Reports of the National Academy of Sciences of Ukraine
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
