Control Systems and Computers

https://doi.org/10.15407/csc.2019.03.003

Control Systems and Computers, 2019, Issue 3 (281), pp. 11-14.

UDC 519.816

N.K. TYMOFIJEVA, Doctor of Technical Sciences, chief researcher, 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

ON SOME APPROACHES TO ESTIMATING THE OPTIMAL SOLUTION OF COMBINATORIAL OPTIMIZATION PROBLEMS

Introduction. In combinatorial optimization, the input data based on which the result of the problem solution is evaluated, are random variables and have a disordered structure. The various methods of data analysis, which are available in mathematical statistics, are used for an adequate estimation.

Formulation of the problem. To estimate the result of the combinatorial optimization problems solution, the structure of the input data, which are random variables with a random structure, is recognized, or based on this information, the objective function is modeled. To get an adequate assessment, it is important to choose such approaches data analysis, in which one can get the optimal result in real time.

The proposed approach. The problems of combinatorial optimization are divided into the tasks in which the argument of objective function (combinatorial configuration) is not based on the structure of the input information, but determined on a certain iteration by chance or by certain rules. In this case, the estimation of the result is made on the expression in which the total product of the values of two finite sequence, which is given input information, is calculated. Accordingly, their dependence on the combinatorial configuration is established. This approach is called correlation, and the method of problem solving is iterative. Otherwise, in the process of solving the problem by the input information structure analyzing, a combinatorial configuration is constructed (the argument of the objective function). That is, by identifying the data structure is the optimal (or global) solution. This method is based on the recognition of the input information structure. There are also methods in which the argument of objective function is constructed in the process of input information recognizing, and the result is estimated by the objective function by the correlation of the input data and the argument of the objective function. In recognition problems, measures of similarity are introduced, by which the values (elementary measure of similarity), which form the sequence of input data, are calculated. By the total product of the sequence values (integral degree of similarity) the result is estimated.

Conclusion. Different approaches to the analysis of input information affect the result accuracy and the speed of the algorithm. By methods based on the recognition of the input data structure in comparison with the iterative ones in which the result evaluation is carried out by a correlation approach, the global solution for large dimensions of the problem is often polynomial.

 Download full text! (In Ukrainian)

Keywords: combinatorial optimization, correlation approach for estimating the result, recognition of the structure of the input data, combinatorial configuration, objective function.

1. Ga’jdychev, I.P., 2001. Analiz i obrabotka dannyx. Spetsialny’j spranothnyk. Sankt-Peterburg, PITER, 752 p. (In Russian).
2. Vintsuk, T.K., 1987. Analiz, raspoznavanie i interpretatsija rethevyx signalov. K.: Nauk. dumka, 262 p. (In Ukrainian).
3. Schlesinger, M., Hlavac, V., 2002. Ten Lectures on Statistical and Structural Pattern Recognition. Computational Imaging and Vision, 24. Kluwer Academic Publishers – Dordrecht, Boston, London, 520 p.
   https://doi.org/10.1007/978-94-017-3217-8
4. Tymofijeva, N.K., 2007. Teoretyko-thyslovi metody rozvjazannja zadath kombinatorno’j optymizatsiji. Avtoref. dys…dokt. texn. nauk, In-t kibernetyky im. V.M. Glushkova NAN Ukrajiny, Kyiv, 32 p. (In Ukrainian).
5. Papadimidriu, X., 1985. Kombinatornaja optimizatsija. Algoritmy i slojnoct. Per. s angl. M.: Mir, 510 p. (In Russian).
6. Tymofijeva, N.K., 2016. “The Proof of the Algorithms Convergence for Combinatorial Optimization with the Using Subclasses of the Solved Problems”. Upravlâûŝie sistemy i mašiny, 2, pp. 5-21, 27. (In Ukrainian).
   https://doi.org/10.15407/usim.2016.02.005
7. Tymofijeva, N.K., 2008. “Method of Structurally-Alphabe­tical Search and Subclasses of Solvable Problem From the Class of the Travelling Salesman Problem”. Upravlâûŝie sistemy i mašiny, 4, pp. 20–36. (In Ukrainian).
8. Hardi, G.G., Litvuld, Dj.E., Polia, G., 1948. Neravenstva. M.: Gos. iz-vo inostr. lit., 456 p. (In Russian).
9. Timofeeva, N.K., 2009. “On Nature of Uncertainty and Variable Criteria in the Partition Problems”. Journal of Automation and Information Sciences, 9, pp. 26-38. DOI: 10.1615/JAutomatInfScien.v41.i9.30.
   https://doi.org/10.1615/JAutomatInfScien.v41.i9.30

Received 27.01.2019