On the Dynamic Problem of Optimal Set Partitioning with Determination of Subset Center Coordinates
Abstract
Relevance. Optimal set partitioning is one of the key problems in modern applied mathematics and optimization theory, with wide-ranging applications in logistics, computer science, bioengineering, complex systems modeling, and artificial intelligence. Of particular interest are dynamic variants of set partitioning problems, where the conditions of the problem change over time, and the partitioning must adapt to the evolving system dynamics. In the vast majority of applied problems, optimal set partitioning is directly linked to the minimization of an objective functional, which inherently depends not only on the shapes or contours of the subsets but also on other defining parameters that are crucial for determining the desired subsets. In classical formulations, such parameters often include the centers of the subsets. Practical applications of problems in this form arise in economics, logistics, medicine, architecture, and other areas of human activity.
Objective. The main goal of this study is to formulate a single-product dynamic optimal set partitioning problem with the determination of the coordinates of the centers of the resulting subsets, to develop an algorithm for solving the dynamic problem, to conduct a numerical experiment, and to analyze the obtained results in order to confirm their reliability.
Methods. The primary research methods used in this work include optimization theory techniques, qualitative theory of differential equations, and numerical methods for solving optimization problems.
Results. The main results of the study include the formulation of a single-product dynamic optimal set partitioning problem with determination of subset center coordinates, the development of a solution algorithm, the outcomes of the numerical experiment, and the analysis of the results obtained.
Conclusions. This article presents a novel dynamic optimal set partitioning problem with determination of subset center coordinates. An algorithm for solving the problem is proposed, and a numerical experiment is conducted. The results confirm the validity of the proposed approach and demonstrate its potential applicability to solving real-world problems.
Downloads
References
/References
E. M. Kiseleva, “The emergence and formation of the theory of optimal set partitioning for sets of the n-dimensional Euclidean space. Theory and application,” J. Autom. Inf. Sci., vol. 50, no. 9, pp. 1–24, 2018. doi: 10.1615/jautomatinfscien.v50.i9.10
O. M. Kiselova, Stanovlennia ta rozvytok teorii optymalnoho rozbyttia mnozhyn. Teoretychni i praktychni zastosuvannia: monohrafiia. Dnipro, Ukraine: Lira, 2018. [in Ukrainian]
E. M. Kiseleva, L. S. Koriashkina, and T. A. Shevchenko, “Solving the dynamic optimal set partitioning problem with arrangement of centers of subsets,” Cybern. Syst. Anal., vol. 50, no. 6, pp. 842–853, 2014. doi: 10.1007/s10559-014-9675-8
E. Kiseleva, O. Prytomanova, and L. Hart, “Solving a two-stage continuous-discrete problem of optimal partitioning-allocation with the subsets centers placement,” Open Comput. Sci., vol. 10, pp. 124–136, 2020. Available: https://www.degruyter.com/view/journals/comp/10/1/article-p124.xml
E. M. Kiseleva and N. Z. Shor, Continuous Problems of Optimal Set Partitioning: Theory, Algorithms, Applications. Kyiv, Ukraine: Naukova Dumka, 2005.
E. M. Kiseleva, O. M. Prytomanova, and S. A. Us, “Solving a two-stage continuous-discrete optimal partitioning-distribution problem with a given position of the subsets centers,” Cybern. Syst. Anal., vol. 56, no. 1, pp. 3–15, 2020. doi: 10.1007/s10559-020-00215-y
E. M. Kiseleva, “Solution of the problem of optimal partitioning including allocation of the centers of gravity of the subsets,” Comput. Math. Math. Phys., vol. 29, no. 3, pp. 47–56, 1989. doi: 10.1016/0041-5553(89)90146-8
E. Kiseleva, L. Hart, O. Prytomanova, and O. Kuzenkov, “An algorithm to construct generalized Voronoi diagrams with fuzzy parameters based on the theory of optimal partitioning and neuro-fuzzy technologies,” in Proc. 8th Int. Conf. Mathematics. Information Technologies. Education (MoMLeT&DS-2019), Shatsk, Ukraine, Jun. 2–4, 2019, pp. 148–162. [Online]. Available: https://ceur-ws.org/Vol-2386/paper12.pdf
G. Buttazzo and G. Dal Maso, “An existence result for a class of shape optimization problems,” Arch. Ration. Mech. Anal., 1993.
L. Caffarelli and F.-H. Lin, “An optimal partition problem for eigenvalues,” J. Sci. Comput., 2007.
M. Conti, S. Terracini, and G. Verzini, “On a class of optimal partition problems related to the Fucik spectrum and to the monotonicity formulae,” Calc. Var. Partial Differ. Equ., 2005.
M. Burger, B. Hackl, and W. Ring, “Incorporating topological derivatives into level set methods,” J. Comput. Phys., 2004.
S. Amstutz and A. A. Novotny, Topological Optimization of Structures. Berlin, Germany: Springer, 2010.
R. T. Rockafellar, Convex Analysis. Princeton, NJ, USA: Princeton Univ. Press, 1973. doi: 10.1017/S0013091500010142
A. Dumas and F. Santambrogio, “Optimal trajectories in L1 and under L1 penalizations,” Comptes Rendus Math., vol. 362, no. G6, pp. 657–692, 2024.
Kiseleva E. M. The emergence and formation of the theory of optimal set partitioning for sets of the n-dimensional Euclidean space. Theory and application // Journal of Automation and Information Sciences. – 2018. – Vol. 50, № 9. – P. 1–24. – DOI: 10.1615/jautomatinfscien.v50.i9.10.
Кісельова О. М. Становлення та розвиток теорії оптимального розбиття множин. Теоретичні і практичні застосування : монографія / О. М. Кісельова. – Дніпро : Ліра, 2018. – 532 с.
Kiseleva E. M., Koriashkina L. S., Shevchenko T. A. Solving the dynamic optimal set partitioning problem with arrangement of centers of subsets // Cybernetics and Systems Analysis. – 2014. – Vol. 50, № 6. – P. 842–853. – DOI: 10.1007/s10559-014-9675-8.
Kiseleva E., Prytomanova O., Hart L. Solving a Two-stage Continuous-discrete Problem of Optimal Partitioning-Allocation with the Subsets Centers Placement // Open Computer Science. – 2020. – Vol. 10. – P. 124–136. –URL: https://www.degruyter.com/view/journals/comp/10/1/article-p124.xml.
Kiseleva E. M., Shor N. Z. Continuous problems of optimal set partitioning: theory, algorithms, applications / E. M. Kiseleva, N. Z. Shor. – К. : Наукова думка, 2005. – 564 p.
Kiseleva E. M., Prytomanova O. M., Us S. A. Solving a two-stage continuous-discrete optimal partitioning-distribution problem with a given position of the subsets centers // Cybernetics and Systems Analysis. – 2020. – Vol. 56, № 1. – P. 3–15. – DOI: 10.1007/s10559-020-00215-y.
Kiseleva E. M. Solution of the problem of optimal partitioning including allocation of the centers of gravity of the Subsets // Computational Mathematics and Mathematical Physics. – 1989. – Vol. 29, № 3. – P. 47–56. – DOI: 10.1016/0041-5553(89)90146-8.
Kiseleva E., Hart L., Prytomanova O., Kuzenkov O. An algorithm to construct generalized Voronoi diagrams with fuzzy parameters based on the theory of optimal partitioning and neuro-fuzzy technologies // Workshop Proceedings of the 8th International Conference on “Mathematics. Information Technologies. Education”, MoMLeT&DS-2019, Shatsk, Ukraine, June 2–4, 2019. – P. 148–162. – URL: https://ceur-ws.org/Vol-2386/paper12.pdf.
Buttazzo G., Dal Maso G. An existence result for a class of shape optimization problems // Archive for Rational Mechanics and Analysis. – 1993.
Caffarelli L., Lin F.-H. An optimal partition problem for eigenvalues // Journal of Scientific Computing. – 2007.
Conti M., Terracini S., Verzini G. On a class of optimal partition problems related to the Fucik spectrum and to the monotonicity formulae // Calculus of Variations and Partial Differential Equations. – 2005.
Burger M., Hackl B., Ring W. Incorporating topological derivatives into level set methods // Journal of Computational Physics. – 2004.
Amstutz S., Novotny A. A. Topological optimization of structures. – Berlin : Springer, 2010.
Rockafellar R. T. Convex Analysis / R. T. Rockafellar. – Princeton University Press, 1973. – DOI: 10.1017/S0013091500010142.
Dumas A., Santambrogio F. Optimal trajectories in L1 and under L1 penalizations // Comptes Rendus. Mathématique. – 2024. – Vol. 362, Issue G6. – P. 657–692.
