THE STUDY OF THE INFLUENCE OF ASYMMETRY ON THE COMPLEXITY OF SOLVING THE TRAVELING SALESMAN PROBLEM BY THE BRANCH AND BOUND METHOD
Abstract
The traveling salesman problem is the one of the most famous combinatorial optimization problems. This problem is important and at the same time difficult to solve, due to the exponential complexity of the exact methods of solution. It occurs in an extensive class of applications: in the construction of optimal motion schemes, recognition of tracks and images. However, a number of scientific studies, in particular, genetics and bioinformatics, require an accurate solution. This study is concerned with the problem of asymmetry influence on the complexity of the solution, which obtained with the classical implementation of branches and bounds method. Since the study requires the analysis of numerous experimental data, there is a need to increase the speed of calculations. The selected approach using branch and bounds method allows gaining an extra speed of search in decision tree by maintaining in-memory state of the active list nodes of the tree. The efficiency of the implementation of the algorithm is also affected by the choice of data structures for the rapid finding of the next vertex under consideration. Based on the results and the analysis, the dependence of the complexity of the problem solution on the asymmetry of the matrix is established. Some asymmetry options reduce the complexity of the solution. The study of the influence of asymmetry on the traveling salesman problem’s complexity on the example of the classical solution algorithm – the method of branches and bounds – is of interest to further predictive analysis of the complexity of individual problems.
References
[2] Tang N.C., Chilkoti A. Combinatorial codon scrambling enables scalable gene synthesis and amplification of repetitive proteins. Nature Materials. 2016; 15(4):419-424. (In Eng.) DOI: 10.1038/nmat4521
[3] Kostevich L.S. Mathematical programming: information technologies of optimal solutions. Mn.: Novoye znaniye, 2003. (In Russ.)
[4] Goodman S.E., Hedetniemi S.T. Introduction to the Design and Analysis of Algorithms. NY: McGraw-Hill, 1977. (In Eng.)
[5] Ulyanov M.V., Fomichev M.I. Resource characteristics of ways to organize a decision tree in the branch-andbound method for the traveling salesmen problem. Business Informatics. 2015; 4(34):38-46. (In Eng.) DOI: 10.17323/1998-0663.2015.4.38.46
[6] Goloveshkin V.A., Zhukova G.N., Ulyanov M.V., Fomichev M.I. Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data. Automation and Remote Control. 2018; 79(7):1296-1310. (In Eng.) DOI: 10.1134/S0005117918070093
[7] Lobjois L., Lemaitre M. Branch and Bound Algorithm Selection by Performance Prediction. Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98). American Association for Artificial Intelligence, AAAI Press, Menlo Park, CA, 1998. Available at: https://aaai.org/Papers/AAAI/1998/AAAI98-050.pdf (accessed 13.01.2019). (In Eng.)
[8] Bektaş T., Gouveia L., Martínez-Sykora A., Salazar-González J. Balanced vehicle routing: Polyhedral analysis and branch-and-cut algorithm. European Journal of Operational Research. 2019; 273(2):452-463. (In Eng.) DOI: 10.1016/j.ejor.2018.08.034
[9] Arigliano A., Ghiani G., Grieco A., Guerriero E., Plana I. Time-dependent asymmetric traveling salesman problem with time windows: Properties and an exact algorithm. Discrete Applied Mathematics. 2019; 261:28-39. (In Eng.) DOI: 10.1016/j.dam.2018.09.017
[10] Hore S., Chatterjee A., Dewanji A. Improving variable neighborhood search to solve the traveling salesman problem. Applied Soft Computing. 2018; 68:83-91. (In Eng.) DOI: 10.1016/j.asoc.2018.03.048
[11] Gouveia L., Leitner M., Ruthmair M. Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman Problem. European Journal of Operational Research. 2017; 262(3):908-928. DOI: 10.1016/j.ejor.2017.04.061
[12] Huang Y., Zhong C. Detecting list-colored graph motifs in biological networks using branch-and-bound strategy. Computers in Biology and Medicine. 2019; 107:1-9. (In Eng.) DOI: 10.1016/j.compbiomed.2019.01.025
[13] Toriello A. Optimal Toll Design: A Lower Bound Framework for the Asymmetric Traveling Salesman Problem. Mathematical Programming. 2014; 144(1-2):247-264. (In Eng.) DOI: 10.1007/s10107-013-0631-6
[14] Sergeev S. Nonlinear resolving functions for the travelling salesman problem. Automation and Remote Control. 2013; 74(6):978-994. (In Eng.) DOI: 10.1134/S0005117913060088
[15] Charikar M., Goemans M.X., Karloff H. On the Integrality Ratio for the Asymmetric Traveling Salesman Problem. Mathematics of Operations Research. 2006; 31(2):245-252. DOI: 10.1287/moor.1060.0191
[16] Subramanyam A., Gounaris C. A branch-and-cut framework for the consistent traveling salesman problem. European Journal of Operational Research. 2016; 248(2):384-395. (In Eng.) DOI: 10.1016/j.ejor.2015.07.030
[17] Goloveshkin V.A., Zhukova G.N., Ulyanov M.V., Fomichev M.I. The estimation of the complexity of solving a particular travelling salesman problem by quantile-based measures for skewness and kurtosis. International Journal of Open Information Technologies. 2016; 4(12):7-12. Available at: https://elibrary.ru/item.asp?id=27543353 (accessed 13.01.2019). . (In Russ.)
[18] Liśkiewicz M., Schuster M. A new upper bound for the traveling salesman problem in cubic graphs. Journal of Discrete Algorithms. 2014; 27:1-20. (In Eng.) DOI: 10.1016/j.jda.2014.02.001
[19] Kara I., Derya T. Formulations for Minimizing Tour Duration of the Traveling Salesman Problem with Time Windows. Procedia Economics and Finance. 2015; 26:1026-1034. (In Eng.) DOI: 10.1016/S2212-5671(15)00926-0
[20] LaRusic J., Punnen A.P. The asymmetric bottleneck traveling salesman problem: Algorithms, complexity and empirical analysis. Computers & Operations Research. 2014; 43:20-35. (In Eng.) DOI: 10.1016/j.cor.2013.08.005
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
