Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2016.02.005

Upr. sist. maš., 2016, Issue 2 (262), pp. 5-21, 27.

UDC УДК 519.816

Tymofejeva Nadeshda К., Doctor of Engineering Sciences, Senior Researcher,  International Research and Training Centre of Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, 
E-mail: tymnad@gmail.com

The Proof of the Algorithms Convergence for Combinatorial Optimization with the Using Subclasses of the Solved Problems

Introduction. The proof of the approximate solutions convergence sequence to a global solution of the combinatorial optimization problem, which is based on a particular algorithm, is rather complicated problem. This is due to the fact that some classes of problems are unsolvable because of their computational complexity. A lot of researches are devoted to the problem of the methods and algorithms convergence within the mathematical programming. They enter the formal level features required and sufficient conditions for their convergence.

Method. The original way to prove some convergence combinatorial optimization methods, based on recognition of the structure of input
data (structure-alphabetical search method nearest neighbor method, “greedy” algorithm) is presented. For this purpose, the subclasses of the traveling salesman problems is used. A sequence of the convergence solutions that are built specifically is proved. 

To assess the methods accuracy, which are decided on a set of permutations, the input data of combinatorial optimization problems defines the functions of the natural argument, one of which is combinatorial. This allows to define a set of values of the objective function for basic problem and to establish some error of interpretation algorithm.

Results and Conclusion. An solvable case for the traveling salesman problem is shown, in which the input data requires the linear combinatorial function for which analytically the global minimum and maximum are found. Using this case proves that the convergence of a solutions sequence built by the structural alphabet search for the traveling salesman problem is close to zero. The optimal solution for subclasses coincides with the global. The speed of the described method is polynomial of computational complexity. The convergence of the nearest neighbor method and of the “greedy” algorithm depends on the structure of input data. For some, the solution structures coincides with the global, while others may be far from optimal.

Download full text!

Keywords: combinatorial optimization, combinatorial configuration, objective function, traveling salesman problem, structure-alphabetical search method, nearest neighbor method, «greedy» algorithm.

1. Karmanov, V.G., 1986. Matematicheskoye programmirovaniye. M.: Nauka, 286 p. (In Russian).
2. Livshits, Ye.D., 2011. Skhodimost’ zhadnykh algoritmov: Avtoref. dis. … d-ra. fiz.-mat. nauk. Ros. un-t druzhby narodov. M., 34 p. (In Russian).
3. Polyak, B.G., 1076. “Skhodimost’ i skorost’ skhodimosti interativnykh stokhasticheskikh algoritmov”. Avtomatika i telemekhanika, T. 1, 12, pp. 83–94. (In Russian).
4. Heche, F., Kotsovskyy, V., Kovalov, S. et. al., 2007. “Pro zbizhnistʹ spektralʹnoho alhorytmu navchannya neyronnykh elementiv”. Visn. Nats. un-tu “Lviv. politekhnika”, 604, pp. 187–194. (In Ukrainian).
5. Ivanov, V., 2014. “A short proof that NP is not P”. Int. J. of Pure and Applied Mathematics, 94 (1), pp. 81–88.
   https://doi.org/10.12732/ijpam.v94i1.9
6. Tymofiyeva, N.K., 2007. Teoretyko-chyslovi metody rozv’yazannya zadach kombinatornoyi optymizatsiyi: Avtoref. dys. … d-ra. tekhn. nauk. In-t kibernetyky im. V.M. Hlushkova NAN Ukrayiny, K., 32 p. (In Ukrainian).
7. Tymofiyeva, N.K., 2015. “Pro metody kombinatornoyi optymizatsiyi, shcho gruntuyutʹsya na rozpiznavanni vkhidnoyi informatsiyi, evrystychni alhorytmy ta obchyslyuvalʹnyy intelekt”. Visn. Vinnytsʹk. politekhnichn. in-tu, 2, pp. 106–111. (In Ukrainian).
8. Ivakhnenko, A.G., 1971. Sistemy evristicheskoy samoorganizatsii v tekhnicheskoy kibernetike. Kiyev: Tekhnika, 392 p. (In Russian).
9. Papadimitriu, K.H., Stayglits, K., 1985. Kombinatornaya optimizatsiya. Algoritmy i slozhnost. M.: Mir, 510 p. (In Russian).
10. Timofeyeva, N.K., 1998. “Opredeleniye mnozhestva znacheniy tselevoy funktsii v zadachakh diskretnoy optimizatsii”. Kibernetika i vycislitelnaa tehnika. Sb. nauch. tr., 120, pp. 37–43. (In Russian).
11. Khardi, G.G., Littlvud, Dzh.Ye., Polia, G., 1948. Neravenstva. M.: Gos. izd-vo inostr. lit., 456 p. (In Russian).
12. Tymofiyeva, N.K., 2015. “Vykorystannya strukturnoho peretvorennya vkhidnykh danykh dlya zvedennya nerozv’yaznykh zadach kombinatornoyi optymizatsiyi do rozv’yaznykh”. Kombinatorni konfihuratsiyi ta yikh zastosuvannya: Materialy desyatoho Mizhvuz. nauk.-prakt. sem. (17–18 kvitnya 2015 r.). Kirovohrad: Kirovohr. tekhn. un-t, pp. 94–99. (In Ukrainian).
13. Tymofiyeva, N.K., 2008. “Metod strukturno-alfavitnoho poshuku ta pidklasy rozvyaznykh zadach iz klasu zadachi komivoyazhera”. Upravlausie sistemy i masiny, 4, pp. 20–36. (In Ukrainian).
14. Ore, O., 1980. Teoriya grafov. M.: Nauka, 336 p. (In Russian).
15. Timofeyeva, N.K., 1993. “Nakhozhdeniye optimal’nogo resheniya v zadache kommivoyazhera”. Programmno-algoritmicheskoye obespecheniye resheniya zadach priklad-noy matematiki. K.: In-t kibernetiki im. V.M. Glushkova AN Ukrainy, pp. 21–26. (In Russian).

Received  15.03.2016