On the Classical Version of the Branch and Bound Method
Abstract
In the computer literature, a lot of problems are described that can be called discrete optimization problems: from encrypting information on the Internet (including creating programs for digital cryptocurrencies) before searching for “interests” groups in social networks. Often, these problems are very difficult to solve on a computer, hence they are called “intractable”. More precisely, the possible approaches to quickly solving these problems are difficult to solve (to describe algorithms, to program); the brute force solution, as a rule, is programmed simply, but the corresponding program works much slower. Almost every one of these intractable problems can be called a mathematical model. At the same time, both the model itself and the algorithms designed to solve it are often created for one subject area, but they can also be used in many other areas. An example of such a model is the traveling salesman problem. The peculiarity of the problem is that, given the relative simplicity of its formulation, finding the optimal solution (the optimal route). This problem is very difficult and belongs to the so-called class of NP-complete problems. Moreover, according to the existing classification, the traveling salesman problem is an example of an optimization problem that is an example of the most complex subclass of this class.
However, the main subject of the paper is not the problem, but the method of its soluti- on, i.e. the branch and bound method. It consists of several related heuristics, and in the monographs, such a multi-heuristic branch and bound method was apparently not previously noted: the developers of algorithms and programs should have understood this themselves. At the same time, the method itself can be applied (with minor changes) to many other discrete optimization problems.
So, the classical version of branch and bound method is the main subject of this paper, but also important is the second subject, i.e. the traveling salesman problem, also in the classical formulation. The paper deals with the application of the branch and bound method in solving the traveling salesman problem, and about this application, we can also use the word “classical”. However, in addition to the classic version of this implementation, we consider some new heuristics, related to the need to develop real-time algorithms.
References
M. R. Garey and D. S. Johnson, Computers and Intractability, Moscow: Mir, 1982 (in Russian).
S. E. Goodman and S. T. Hedetniemi, Introduction to the Design and Analysis of Algorithms, Moscow: Mir, 1981 (in Russian).
J. Hromkovic, ˇ Theoretical computer science: introduction to Automata, computability, complexity, algori- thmics, randomization, communication, and cryptography, St. Petersburg, Russia: BKhV-Peterburg, 2010 (in Russian).
J. Hromkovic, ˇ Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomi- zation, Approximation, and Heuristics, Berlin: Springer, 2004.
R. Gera, S. Hedetniemi, and C. Larson, eds., Graph Theory. Favorite Conjectures and Open Problems, vol. 1, Berlin: Springer, 2016.
R. Gera, S. Hedetniemi, and C. Larson, eds., Graph Theory. Favorite Conjectures and Open Problems, vol. 2, Berlin: Springer, 2016.
B. F. Melnikov, E. A. Melnikova, and S. V. Pivneva, “Mahjongg Solitaire: a High School Student Scientific Project, Containing Elements of Artificial Intelligence,” Computer tools in education, no. 5, pp. 41–51, 2018 (in Russian); doi: 10.32603/2071-2340-2018-5-41-51
M. E. Abramyan, B. F. Melnikov, and E. A. Melnikova, “Finite Automata Table: a Science Project for High School Students,” Computer tools in education, no. 2, pp. 87–107, 2019 (in Russian); doi:10.32603/2071- 2340-2019-2-87-107
D. Applegate, R. Bixby, V. Chvatal, and W. Cook, The Traveling Salesman Problem: A Computational Study, NJ: Princeton University Press, 2007.
G. Gutin and A. Punnen, eds. Combinatorial Optimization. The Traveling Salesman Problem and Its Variations, Berlin: Springer, 2007.
Th. H. Cormen, Ch. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Moscow: Viljams, 2013 (in Russian).
V. N. Lyalikov, “Kompleks programm dlya issledovaniya metodov resheniya zadachi o kommi- voyazhere. Dissertation of the candidate of technical sciences,”, Ulyanovsk State Technical University, Ul’yanovsk, Russia, 2008 (in Russian).
M. Dorigo and L. M. Gambardella, “Ant Colonies for the Traveling Salesman Problem,” Biosystems, vol. 43, no. 2, pp. 73–81, 1997.
G. Bulynin, B. F. Melnikov, V. Y. Meshchanin, and Y. Y. Terentyeva, “Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them,” Informatizatsiya i svyaz’, no. 1, pp. 34–40, 2020 (in Russian); doi: 10.34219/2078-8320- 2020-11-1-34-40
B. F. Melnikov, V. Y. Meshchanin, and Y. Y. Terentyeva, “Implementation of optimality criteria in the design of communication networks,” Journal of Physics: Conference Series, vol. 1515, no. 4, p. 042093, 2020; doi: 10.1088/1742-6596/1515/4/042093
B. F. Melnikov and M. A. Trenina, “The application of the branch and bound method in the problem of reconstructing the matrix of distances between DNA strings,” International Journal of Open Information Technologies, vol. 6, no. 8, pp. 1–13, 2018 (in Russian).
B. Melnikov, M. Trenina, and E. Melnikova, “Different Approaches to Solving the Problem of Reconstructing the Distance Matrix Between DNA Chains,” in Proc. SITITO 2018: Modern Information Technology and IT Education, vol. 1201, 2020, pp. 211–223; doi: 10.1007/978-3-030-46895- 8_17
B. F. Melnikov, E. V. Davydova, A. V. Nichiporchuk, and M. A. Trenina, “Clustering of situations in the algorithms for solving the traveling salesman problem and its application in some applied tasks. Part II. List metrics and some related optimization problems,” University proceedings. Volga region, vol. 4, no. 48, pp. 62–77, 2018 (in Russian).
B. F. Melnikov and A. N. Radionov, “O vybore strategii v nedeterminirovannykh antagonisticheskikh igrakh” [On the choice of strategy in nondeterministic antagonistic games], Izvestiya RAN. Programmi- rovanie, no. 5, pp. 55–62, 1998 (in Russian).
B. Melnikov and N. Romanov, “Eshche raz ob evristikakh dlya zadachi kommivoyazhera” [Once again about heuristics for the traveling salesman problem], Teoreticheskie problemy informatiki i ee prilozhenii, vol. 4, pp. 81–89, 2001 (in Russian).
B. F. Melnikov and S. V. Pivneva, “Prinyatie reshenii v prikladnykh zadachakh s primeneniem dinami- cheski podobnykh funktsii riska” [Decision making in applied problems using dynamically similar risk functions], Vestnik transporta Povolzhya, vol. 3, no. 23, pp. 28a–33, 2010 (in Russian).
N. Wirth, Algorithms + Data Structures, Moscow: Mir, 1989 (in Russian).
Kh. Sigal and A. P. Ivanova, Introduction to Applied Discrete Programming: Models and Computational Algorithms, Moscow: Fizmatlit, 2007 (in Russian).
B. Melnikov and E. Melnikova, “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, no. 2, pp. 16–20, 2007 (in Russian).
This work is licensed under a Creative Commons Attribution 4.0 International License.
