About the Object-Oriented Implementation of the Branch and Boundary Method for the Travelling Salesman Problem
Part I
Abstract
Many discrete optimization problems are very difficult to solve on a computer; hence they are titled "intractable". More precisely, the possible approaches to solving these problems quickly are difficult to solve (for describing algorithms, for programming), and the iterative solution, as a rule, is programmed simply, but the corresponding program works much slower.
This paper, like the previous one on this topic, can be called "methodical". In the previous paper on this topic, we described our approach to the method of branches and boundaries, primarily for the classical traveling salesman problem. We considered both the classical heuristics of this method and their modern interpretation. The main purpose of this article is quite different from that of the previous article: now we consider the software aspects of the implementation of this method.
We executed the software package in C++ – and at the same time tried to use all such language features that can be used for programming practically any algorithms of discrete mathematics; of course, first and foremost we mean object-oriented capabilities.
At the end of the article (in Part II), we present some results of computational experiments. And in conclusion, we consider several interesting topics for further study by students: both papers (the previous one and the present one) describe only the beginning of a very large number of possible topics related to the application of the branches and bounds method for discrete optimization problems, in particular, with the object-oriented implementation of this method.
References
2. Shen A. Algorithms and Programming: Problems and Solutions. Springer Undergraduate Texts in Mathematics and Technology. Springer, New York, NY; 2010. 272 p. (In Eng.) doi: https://doi.org/10.1007/978-1-4419-1748-5
3. Melnikov B., Trenina M., Melnikova E. Different Approaches to Solving the Problem of Reconstructing the Distance Matrix Between DNA Chains. In: Sukhomlin V., Zubareva E. (eds.) Modern Information Technology and IT Education. SITITO 2018. Communications in Computer and Information Science. Vol. 1201. Springer, Cham; 2020. p. 211-223. (In Eng.) doi: https://doi.org/10.1007/978-3-030-46895-8_17
4. Melnikov B.F., Melnikova E.A., Pivneva S.V. Mahjongg Solitaire: a high-school student scientific project, containing elements of artificial intelligence. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education journal. 2018; (5):41-51. (In Russ., abstract in Eng.) doi: https://doi.org/10.32603/2071-2340-2018-5-41-51
5. Abramyan M.E., Melnikov B.F., Melnikova E.A. Finite automata table: a science project for high school students. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education journal. 2019; (2):87-107. (In Russ., abstract in Eng.) doi: https://doi.org/10.32603/2071-2340-2019-2-86-107
6. Gera R., Hedetniemi S., Larson C. Graph Theory: Favorite Conjectures and Open Problems – 1. Problem Books in Mathematics. Springer, Cham; 2016. 291 p. (In Eng.) doi: https://doi.org/10.1007/978-3-319-31940-7
7. Gera R., Haynes T.W., Hedetniemi S. Graph Theory: Favorite Conjectures and Open Problems – 2. Problem Books in Mathematics. Springer, Cham; 2018. 281 p. (In Eng.) doi: https://doi.org/10.1007/978-3-319-97686-0
8. Hromkovič J. Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg; 2004. 538 p. (In Eng.) doi: https://doi.org/10.1007/978-3-662-05269-3
9. Gutin G., Punnen A.P. The Traveling Salesman Problem and Its Variations. Combinatorial Optimization. Vol. 12. Springer, Boston, MA; 2007. 830 p. (In Eng.) doi: https://doi.org/10.1007/b101971
10. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem. Biosystems. 1997; 43(2):73-81. (In Eng.) doi: https://doi.org/10.1016/S0303-2647(97)01708-5
11. Melnikov B.F., Melnikova E.A. Klasterizatsiya situatsii v algoritmakh realnogo vremeni dlya zadach diskretnoi optimizatsii [Situation Clustering in Real-Time Algorithms for Discrete Optimization Problems]. Sistemy upravleniya i informatsionnye tekhnologii. 2007; (2):16-20. Available at: https://elibrary.ru/item.asp?id=11717006 (accessed 16.05.2022). (In Russ., abstract in Eng.)
12. Bulynin A.G., Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them. Informatizacija i svjaz' = Informatization and Communication. 2020; (1):34-40. (In Russ., abstract in Eng.) doi: https://doi.org/10.34219/2078-8320-2020-11-1-34-40
13. Melnikov B., Dudnikov V., Pivneva S. Heuristic Algorithm and Results of Computational Experiments of Solution of Graph Placement Problem. In: Sukhomlin V., Zubareva E. (eds.) Modern Information Technology and IT Education. SITITO 2017. Communications in Computer and Information Science. Vol. 1204. Springer, Cham; 2021. (In Eng.) doi: https://doi.org/10.1007/978-3-030-78273-3_16
14. Melnikov B., Eyrih S.N. On the approach to combining truncated branch-and-bound method and simulated annealing. Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2010; (1):35-38. Available at: https://www.elibrary.ru/item.asp?id=15199645 (accessed 16.05.2022). (In Russ., abstract in Eng.)
15. Makarkin S.B., Melnikov B.F. Geometricheskie metody reshenija psevdogeometricheskoj versii zadachi kommivojazhera [Geometric methods for solving the pseudo-geometric version of the traveling salesman problem]. Stohasticheskaya optimizaciya v informatike = Stochastic optimization in informatics. 2013; 9(2);54-72. Available at: https://www.elibrary.ru/item.asp?id=20960443 (accessed 16.05.2022). (In Russ., abstract in Eng.)
16. Baumgertner S.V., Melnikov B.F. Multi-heuristic approach for the star-height minimization of non-deterministic finite automata. Proceedings of Voronezh State University. Series: Systems Analysis and Information Technologies. 2010; (1):5-7. Available at: https://elibrary.ru/item.asp?id=15199639 (accessed 16.05.2022). (In Russ., abstract in Eng.)
17. Melnikov B.F., Panin A.G. The parallel implementation of the multiheuristical approach in the nucleotide sequence comparison problem. Science Vector of Togliatti State University. 2012; (4):83-86. Available at: https://elibrary.ru/item.asp?id=18755384 (accessed 16.05.2022). (In Russ., abstract in Eng.)
18. Vakhitova A. The basis automaton for the given regular language. The Korean Journal of Computational and Applied Mathematics. 1999; 6(3):617-624. (In Eng.) doi: https://doi.org/10.1007/BF03009953
19. Hashiguchi K. Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language. In: Albert J.L., Monien B., Artalejo M.R. (eds.) Automata, Languages and Programming. ICALP 1991. Lecture Notes in Computer Science. Vol. 510. Springer, Berlin, Heidelberg; 1991. (In Eng.) doi: https://doi.org/10.1007/3-540-54233-7_170
20. Melnikov B., Melnikova E. On the Classical Version of the Branch and Bound Method. Kompjuternye instrumenty v obrazovanii = Computer Tools in Education journal. 2022; (2):41-58. (In Eng.) doi: https://doi.org/10.32603/2071-2340-2022-2-41-58
21. Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Implementation of optimality criteria in the design of communication networks. Journal of Physics: Conference Series. 2020; 1515:042093. (In Eng.) doi: https://doi.org/10.1088/1742-6596/1515/4/042093
22. Pokorni S., Janković R. Reliability estimation of a complex communication network by simulation. 2011 19thTelecommunications Forum (TELFOR) Proceedings of Papers. IEEE Computer Society; 2011. p. 226-229. (In Eng.) doi: https://doi.org/10.1109/TELFOR.2011.6143532
23. Yu H., Oh J. Anytime 3D Object Reconstruction Using Multi-Modal Variational Autoencoder. IEEE Robotics and Automation Letters. 2022; 7(2):2162-2169. (In Eng.) doi: https://doi.org/10.1109/LRA.2022.3142439
24. Geldenhuys J., van der Merwe B., van Zijl L. Reducing Nondeterministic Finite Automata with SAT Solvers. In: Yli-Jyrä A., Kornai A., Sakarovitch J., Watson B. (eds.) Finite-State Methods and Natural Language Processing. FSMNLP 2009. Lecture Notes in Computer Science. Vol. 6062. Springer, Berlin, Heidelberg; 2010. (In Eng.) doi: https://doi.org/10.1007/978-3-642-14684-8_9
25. Yo-Sub Han. State Elimination Heuristics for Short Regular Expressions. Fundamenta Informaticae. 2013; 128(4):445-462. (In Eng.) doi: https://doi.org/10.3233/FI-2013-952
26. Grandcolas S., Pain-Barre C. A hybrid metaheuristic for the two-dimensional strip packing problem. Annals of Operations Research. 2022; 309(1):79-102. (In Eng.) doi: https://doi.org/10.1007/s10479-021-04226-6
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.
