Continuous extensions on Euclidean combinatorial configurations

Oksana Pichugina ; Sergiy Yakovlev

Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 1 (2022), pp. 3-21.

Résumé

In this paper, we introduce a concept of the Euclidean combinatorial configuration as a mapping of a set of certain objects into a point of Euclidean space. We classify Euclidean combinatorial configurations sets based on their structure and constraints. The proposed typology forms the basis for studying continuous functional representations of combinatorial configurations. Special classes of functional extensions are introduced, their properties are described, and corresponding examples are given.

Bibliographie

[1] Balinski M. L., Hoffman A. J., Polyhedral Combinatorics: Dedicated to the Memory of D. R. Fulkerson, Elsevier Science Ltd, Amsterdam–New York, 1978 | MR

[2] Berge C., Principles of Combinatorics, Academic Press, 2012 | MR

[3] Blum-Smith B., Coskey S., “The fundamental theorem on symmetric polynomials: history's first Whiff of Galois Theory”, The College Mathematics Journal, 48 (2017), 18–29 | DOI | MR | Zbl

[4] Bochnak J., Coste M., Roy M., Real Algebraic Geometry, Springer-Verlag, Berlin, 1998 | MR | Zbl

[5] Emelichev V. A., Kotov V. M., Kuzmin K. G., Lebedeva T. T., Semenova N. V., Sergienko T. I., “Stability and Effective Algorithms for Solving Multiobjective Discrete Optimization Problems with Incomplete Information”, J. Autom. and Inform. Sci., 46 (2014), 27–41 | DOI

[6] Gerasin S. N., Shlyakhov V. V., Yakovlev S. V., “Set coverings and tolerance relations”, Cybern. Syst. Anal., 44 (2008), 333–340 | DOI | MR | Zbl

[7] Gotoh J., Uryasev S., “Two pairs of families of polyhedral norms versus $\ell _p$-norms: proximity and applications in optimization”, Math. Program., 156 (2016), 391–431 | DOI | MR | Zbl

[8] Grande F., On k-level matroids: geometry and combinatorics, Doctor of Natural Sciences Dissertation, Institut fur Mathematik und Informatik, Berlin, 2015

[9] Hartshorne R., Algebraic Geometry, Springer-Verlag, New York, 1983 | MR | Zbl

[10] Grebennik I. V., Kovalenko A. A., Romanova T. E., Urniaieva I. A., Shekhovtsov S. B., “Combinatorial configurations in balance layout optimization problems”, Cybern. Syst. Anal., 54 (2018), 221–231 | DOI | MR | Zbl

[11] Green R. M., “Homology representations arising from the half cube, II”, Journal of Combinatorial Theory, Ser. A, 117 (2010), 1037–1048 | DOI | MR | Zbl

[12] Hillier F. S. et al., “Continuous Approaches for Solving Discrete Optimization Problems”, Handbook on Modelling for Discrete Optimization, 2006, 39–60

[13] Malick J., Roupin F., “On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0-1 quadratic problems leading to quasi-Newton methods”, Mathematical Programming, 140 (2013), 99–124 | DOI | MR | Zbl

[14] Ng K.-M., A continuation approach for solving nonlinear optimization problems with discrete variables, Doctor of Philosophy Thesis, Department of Management Science and Engineering, Stanford University, Stanford, 2003

[15] Pavlikov K., Uryasev S., “CVaR norm and applications in optimization”, Optim. Lett., 8 (2014), 1999–2020 | DOI | MR | Zbl

[16] Pichugina O., “Placement problems in chip design: Modeling and optimization”, 4th International Scientific-Practical Conference Problems of Infocommunications Science and Technology, Proceedings, 2017, 465–473

[17] Pichugina O., Farzad B., “A Human Communication Network Model”, CEUR Workshop Proceedings, 2711, 2016, 33–40

[18] Pichugina O., “New Bounds in Linear Combinatorial Optimization”, CEUR Workshop Proceedings, 2711, 2020, 137–149

[19] Pichugina O. S., Yakovlev S. V., “Continuous approaches to the unconstrained binary quadratic problems”, Mathematical and Computational Approaches in Advancing Modern Science and Engineering, Springer, Cham, 2016, 689–700 | MR | Zbl

[20] Pichugina O. S., Yakovlev S. V., “Convex extensions and continuous functional representations in optimization with their applications”, J. Coupled Syst. Multiscale Dyn., 4 (2016), 129–152 | DOI

[21] Pichugina O. S., Yakovlev S. V., “Continuous representations and functional extensions in combinatorial optimization”, Cybern. Syst. Anal., 52 (2016), 921–930 | DOI | MR | Zbl

[22] Pichugina O. S., Yakovlev S. V., “Functional and analytic representations of the general permutations”, East. Eur. J. Enterp. Technol., 1 (2016), 27–38

[23] Pichugina O., Yakovlev S., “Optimization on polyhedral-spherical sets: Theory and applications”, IEEE 1st Ukraine Conference on Electrical and Computer Engineering, Proceedings, 2017, 1167–1174

[24] Pichugina O. S., Yakovlev S. V., “Continuous representation techniques in combinatorial optimization”, IOSR J. Math., 13 (2017), 12–25 | DOI

[25] Pichugina O., Yakovlev S., “Euclidean combinatorial configurations: continuous representations and convex extensions”, Lecture Notes in Computational Intelligence and Decision Making, Springer, Cham, 2020, 65–80 | DOI | MR

[26] Pichugina O., Yakovlev S., “Quadratic optimization models and convex extensions on permutation matrix set”, Advances in Intelligent Systems and Computing, Springer, Cham, 2020, 231–246 | DOI

[27] Pogorelov A. V., Extrinsic Geometry of Convex Surfaces, American Mathematical Society, Providence, R. I., 1973 | MR | Zbl

[28] Pulleyblank W. R., “Edmonds, matching and the birth of polyhedral combinatorics”, Documenta Mathematica, 2012, 181–197 | MR | Zbl

[29] Sanyal R., Sottile F., Sturmfels B., “Orbitopes”, Mathematika, 57 (2011), 275–314 | DOI | MR | Zbl

[30] Semenova N. V., Kolechkina L. N., Nagirna A. M., “Vector optimization problems with linear criteria over a fuzzy combinatorial set of alternatives”, Cybern. Syst. Anal., 47 (2011), 250–259 | DOI | MR | Zbl

[31] Shekhovtsov S. B., Yakovlev S. V., “Formalization and solution of one class of covering problem in design of control and monitoring systems”, Avtomatika i Telemekhanika, 5 (1989), 160–168 | MR | Zbl

[32] Shor N. Z., Stetsyuk P. I., “Lagrangian bounds in multiextremal polynomial and discrete optimization problems”, J. Global Optim., 23 (2002), 1–41 | DOI | MR | Zbl

[33] Stoyan Y., Romanova T., “Mathematical models of placement optimisation: two- and three-dimensional problems and applications”, Modeling and Optimization in Space Engineering, Springer, New York, 2013, 363–388 | MR | Zbl

[34] Stoyan Y. G., Semkin V. V., Chugay A. M., “Optimization of 3D objects layout into a multiply connected domain with account for shortest distances”, Cybern. Syst. Anal., 50 (2014), 374–385 | DOI | MR | Zbl

[35] Stoyan Yu. G., Sokolovskii V. Z., Yakovlev S. V., “Method of balancing rotating discretely distributed masses”, Energomashinostroenie, 2 (1982), 4–5

[36] Stoyan Y. G., Yakovlev S. V., “Configuration space of geometric objects”, Cybern. Syst. Anal., 54 (2018), 716–726 | DOI | MR | Zbl

[37] Stoyan Y. G., Yakovlev S. V., Mathematical Models and Optimization Methods of Geometric Design, Nauk. Dumka, Kyiv, 2020 | MR

[38] Stoyan Y. G., Yakovlev S. V., Parshin O. V., “Quadratic optimization on combinatorial sets in $R^n$”, Cybern. Syst. Anal., 27 (1991), 561–567 | DOI | MR

[39] Stoyan Y. G., Yakovlev S. V., “Theory and methods of Euclidian combinatorial optimization: current status and prospects”, Cybern. Syst. Anal., 56 (2020), 366–379 | DOI | MR | Zbl

[40] Stoyan Y. G., Yakovlev S. V., Yemets O. A., Valuyskaya O. A., “Construction of convex continuations for functions defined on hypersphere”, Cybern. Syst. Anal., 34 (1998), 176–184 | DOI | MR | Zbl

[41] Vinzant C., Real Algebraic Geometry in Convex Optimization, Doctor of Philosophy Dissertation, University of California, Berkeley, 2011 | MR

[42] Yakovlev S. V., “Bounds on the minimum of convex functions on Euclidean combinatorial sets”, Cybernetics, 25 (1989), 385–391 | DOI | MR | Zbl

[43] Yakovlev S. V., “The theory of convex continuations of functions on vertices of convex polygons”, J. Comp. Math. Math. Phys., 34 (1994), 959–965 | MR | Zbl

[44] Yakovlev S. V., “On a class of problems on covering of a bounded set”, Acta Mathematica Hungarica, 53 (1999), 253–262 | DOI | MR

[45] Yakovlev S. V., “On some classes of spatial configurations of geometric objects and their formalization”, J. Autom. and Inform. Sci., 50 (2018), 73–84 | DOI | MR

[46] Yakovlev S., “Convex extensions in combinatorial optimization and their applications”, Springer Optimization and its Applications, 130 (2017), 567–584 | DOI | MR | Zbl

[47] Yakovlev S. V., “The method of artificial space dilation in problems of optimal packing of geometric objects”, Cybern. Syst. Anal., 53 (2017), 725–731 | DOI | MR | Zbl

[48] Yakovlev S. V., “Formalizing spatial configuration optimization problems with the use of a special function class”, Cybern. Syst. Anal., 55 (2019), 581–589 | DOI | MR | Zbl

[49] Yakovlev S. V., Grebennik I. V., “Localization of solutions of some problems of nonlinear integer optimization”, Cybern. Syst. Anal., 29 (1993), 727–734 | DOI | MR | Zbl

[50] Yakovlev S., Kartashov O., Pichugina O., Koliechkina L., “The Genetic Algorithms in Optimization Problem on Combinatorial Configurations”, International Conference on Innovations in Engineering, Technology and Sciences, Proceedings, 2018, 264–267

[51] Yakovlev S., Kartashov O., Pichugina O., “Optimization on combinatorial configurations using genetic algorithms”, CEUR Workshop Proceedings, 2353, 2019, 28–40

[52] Yakovlev S., Kartashov O., Yarovaya O., “On class of genetic algorithms in optimization problems on combinatorial configuration”, IEEE XIII International Scientific and Technical Conference on Computer Sciences and Information Technologies Proceedings, 2018, 374–377

[53] Yakovlev S. V., Pichugina O. S., “Properties of combinatorial optimization problems over polyhedral-spherical sets”, Cybern. Syst. Anal., 54 (2018), 99–109 | DOI | MR | Zbl

[54] Yakovlev S., Pichugina O., Koliechkina L., “A lower bound for optimization of arbitrary function on permutations”, Lecture Notes in Computational Intelligence and Decision Making, Springer, Cham, 2020, 195–212

[55] Yakovlev S., Pichugina O., Yarovaya O., “On optimization problems on the polyhedral-spherical configurations with their properties”, IEEE First International Conference on System Analysis and Intelligent Computing, Proceedings, 2018, 94–100 | MR

[56] Yakovlev S., Pichugina O., Yarovaya O., “Polyhedral-spherical configurations in discrete optimization problems”, Journal of Automation and Information Sciences, 51 (2019), 26–40 | DOI | MR

[57] Yakovlev S. V., Valuiskaya O. A., “Optimization of linear functions at the vertices of a permutation polyhedron with additional linear constraints”, Ukr. Math. J., 53 (2001), 1535–1545 | DOI | MR | Zbl

[58] Yemelichev V. A., Kovalev M. M., Kravtsov M. K., Polytopes, graphs and optimisation, Cambridge University Press, Cambridge, 1984 | MR | Zbl

[59] Ziegler G. M., Lectures on Polytopes, Springer, New York, 2013 | MR