Control Systems and Computers, N4, 2023, Article 1
https://doi.org/10.15407/csc.2023.04.003
Control Systems and Computers, 2023, Issue 4 (304), pp. 3-11
UDC 519.816
Tymofijeva N.К., Doctor of Sciences (Eng.), Chief researcher, Head of the department, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, tymnad@gmail.com
Objective Function in Combinatorial Optimization and Its Properties
Introduction Some properties of combinatorial optimization problems are described, which affect the regularity of changes in the values of the objective function regardless of the input data. It is shown that this regularity depends on the arrangement of combinatorial configurations, a certain structure of input information, the transposition of permutation elements and the symmetry of combinatorial sets (argument). In problems that are solved on permutations. and a subset of isomorphic combinatorial configurations, the class of the objective function is determined depending on their ordering and the structure of the input data.
Formulation of the problem. There are works where, in combinatorial optimization, the change in the values of the objective function is investigated depending on the special structure of the input information. These studies are related to the selection of subclasses of solvable problems, and various structures are generalized for which the objective function changes in the same way. The task is to identify the parameters of problems of this class, in which the input data do not affect the pattern of changes in the values of the objective function
The proposed approach. To identify the parameters under which the input data do not affect the pattern of changes in the objective function values in combinatorial optimization, this pattern is analyzed from the arrangement of permutations, the transposition of its elements, and the structure of the input information. The change of the values of the objective function from the structure of its argument (the structure of combinatorial sets) is also investigated.
Conclusion. Knowing the properties of combinatorial functions allows you to establish a change in the values of the target function depending on the transposition of the elements in the permutation, on the arrangement of combinatorial configurations. If the combinatorial set consists of one subset of isomorphic combinatorial configurations (permutations), then the set of values of the objective function follows the rules characteristic of permutations. If the set consists of subsets of isomorphic combinatorial configurations, then they can be ordered in such a way that the objective function for this ordering varies as piecewise monotonic functions regardless of the input data, and for the isomorphic subset it varies as in problems whose objective function argument is the permutation.
Download full text! (On Ukrainian)
Keywords: combinatorial optimization, combinatorial configuration, objective function, transposition, traveling salesman problem, destination problem, clustering problem.
- Papadimidriu, X., Sta’jglits, K. (1985). Kombinatornaja optimizatsija. Algoritmy i slojnost / Per. s angl. M.: Mir, 510 p.
- Geri, M., Djonson, D. (1982). Vythislitelnye mashiny i trudnoreshaemye zadathi / Per. s angl. M.: Mir, 416 p.
- Tymofijeva, N.K. (2008). “Metod strukturno-alfavitnogo podhuku ta pidklasy rozv’jaznyx zadath iz klasu zadath komivojajera”. Upravlyayushchie Sistemy i Mashiny. no 4, pp. 20-36 (In Russian).
- Sergienko, I.V., Kaspthitzkaja, M.F. (1981). Modeli i metodu reshenija na EVM kombinatornyx zadath optimizatziji, Kiev: Nauk Dumka, 281 p.
- Vintsuk, T.K. (1987). Analiz, raspoznfvanie i interpretatsija rethevyx signalov. K.: Nauk Dumka, 262 p.
- Bellman, P. (1960). Dinamitheskoje programmirovanije. M.: Isd-vo inostranno’j literatury, 400 p.
- Tymofijeva, N.K. (2007). Teoretyko-thyslovi metody rozvjazannja zadath kombinatorno’j optymizatsiji. Dysertashija na zdobuttja stupenja texnithnyx nauk za spetsialnistju 01.05.02 – matematythne modeljuvannja ta obthysljuvalni metody. Rukopys. ІK im. V.M. Glushkova NAN Ukrainy, Kyiv, 374 p.
- Tymofeeva, N.K. (2002). “O nekotoryx svo’jstvax rasbyeni’j mnojestva na podmnojtstva”. Upravlyayushchie Sistemy i Mashiny, no 5, pp. 6-23 (In Russian).
Received 15.10.2023
