On the application a number of predictors in the branch and bound method (on the example of the random variant of the traveling salesman problem)
Abstract
For the so-called random variant of the traveling salesman problem, there are currently no fast algorithms, including heuristic ones, that give the optimal solution (or close to it); at least for the dimension of the problem exceeding 300. This fundamentally distinguishes the random variant from the so-called geometric variant of the same problem, for which the so-called onion husk algorithms have been known for at least 25 years, giving a close to optimal solution for any dimension. At the same time, the random variant of the traveling salesman problem, as well as the more general pseudo-geometric variant, often represents an acceptable model for applied problems of different classes; this statement can hardly be attributed to the geometric variant, therefore the algorithms for solving the random variant are still important. Also, the relevance of the problem variant considered in the paper follows from its possible applicability in the formulation of options for calculating the so-called viability of the communication network, an integral indicator that is an average indicator of the viability estimates of all possible communication directions determined by a pair of vertices of the communication network graph. Usually, communication network developers strive to ensure that all directions have a backup route; it is assumed that we should check this, and such a check can be made using the algorithm for finding the optimal Hamiltonian cycle. So, it is necessary to be able to solve a random variant of the traveling salesman problem, and, first of all, to describe the so-called anytime algorithms for its solution. For a random variant of the problem (and for both exact and anytime algorithms), the classical approach to its solution is relevant, associated with the use of the branch and bound method. We apply the usual description of this method, but with numerous changes and additions described in our previous publications, as well as in this paper. Apparently, to build successful specific variants of algorithms implementing this method, the most important is the auxiliary algorithm for selecting the separating element (and the last statement applies not only to the traveling salesman problem, but also to any problem solved using the branch and bound method). The auxiliary procedure for selecting a separating element is called a predictor. In this paper, the authors propose a use case for selecting the separating element of an integral assessment using two simplest predictors; at the same time, such an option is easily generalized to the case of a larger number of predictors. The paper briefly describes the results obtained, confirming the improvement of the algorithm of the branch and bound method when using the two predictors under consideration.
Full Text:
PDF (Russian)References
Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. – Berlin, Springer. – 2004. – 318 p.
Hromkovič J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. – Berlin, Springer. – 2003. – 538 p.
Makarkin S.B., Melnikov B.F.: Geometric methods for solving the pseudogeometric version of the traveling salesman problem // Stochastic Optimization in Computer Science. 2013. Vol. 6, No. 2. P. 54–72. (In Russian.)
Makarkin S.B., Melnikov B.F., Trenina M.A.: Application of problem-oriented metrics in geometric algorithms for solving the pseudogeometric version of the traveling salesman problem // Stochastic Optimization in Computer Science. 2014. Vol. 10, No. 1. P. 63–71. (In Russian.)
Makarkin S.B., Melnikov B.F., Trenina M.A.: An approach to solving the pseudogeometric version of the traveling salesman problem // News of higher educational institutions. Volga region. Physical and mathematical sciences. 2015. No. 2 (34). P. 135–147. (In Russian.)
Melnikov B.F., Давыдова Е.В.: Mathematical modeling of increasing the level of safety in case of failures of aviation and space technology // International Journal of Open Information Technologies. 2023. Vol. 6, No. 5. P. 1–6. (In Russian.)
Garey M., Johnson D. Computers and Intractability. A Guide to the Theory of NP-Completeness. – San Francisco, Freeman and Company. – 1979. – 338 p.
Melnikov B.F., Terentyeva Y.Y., Chaykovsky D.A.: On the application of heuristic algorithms for solving the pseudogeometric version of the traveling salesman problem for the design of communication networks // Informatization and Communication. 2023. No. 4. P. 7–16. (In Russian.)
Melnikov B.F., Melnikova E.A.: On the classical version of the branch and bound method // Computer Tools in Education. 2021. No. 1. P. 21– 44. (In Russian.)
Dorigo M., Gambardella L.M.: Ant colony system: A cooperative learning approach to the traveling salesman problem // IEEE Transactions on Evolutionary Computation. 1997. Vol. 1, No. 1. P. 53– 66.
Gutin G., Punnen A. (editors): The Traveling Salesman problem. – Boston, Kluwer Academic Publishers. – 2008. – 856 p.
Rego C., Gamboa D., Glover F., Osterman C.: Traveling salesman problem heuristics: Leading methods, implementations and latest advances // European Journal of Operational Research. 2011. Vol. 211, No. 3. P. 427–441.
Cook W.: In pursuit of the traveling salesman: Mathematics at the limits of computation. – Princeton, Princeton University Press. – 2012. – 248 p.
Lagutin M.B.: Visual mathematical statistics. – Moscow, Binom. Laboratory of Knowledge. – 2012. – 472 p. (In Russian.)
Melnikov B.F., Sayfullina E.F., Terentyeva Y.Y., Churikova N.P.: Application of random graph generation algorithms to study the reliability of communication networks // Informatization and Communication. 2018. No. 1. P. 71–80. (In Russian.)
Bulynin A.G., Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y.: Optimization problems arising in the design of high-dimensional communication networks and some heuristic methods for their solution // Informatization and Communication. 2020. No. 1. P. 34–40. (In Russian.)
Melnikov B.F., Terentyeva Y.Y.: Building an optimal spanning tree as a tool to ensure the stability of the communication network // News of higher educational institutions. Volga region. Technical sciences. 2021. No. 1 (57). P. 36–45. (In Russian.)
Biryukov A.A.: Information security: defense and attack. – Moscow,
DMK Press. – 2013. – 472 p. (In Russian.)
Popkov G.V.: On the issue of assessing the stability of the functioning of the elements of the communication network // Software Products and Systems. (In Russian.) 2018. No. 2. P. 316–320.
Popkov G.V., Ovchinnikova E.A.: On the issue of using a scenario approach in the formation of a model of threats to information security of multiservice communication networks // Telecommunications. 2022. No. 9. P. 21–27. (In Russian.)
Russell S., Norvig P. Artificial Intelligence: A Modern Approach. Englewood Cliffs: Pearson Publ., 2009. 1152 p.
Baumgärtner S.V., Melnikov B.F.: A multiheuristic approach to the problem of the star-height minimization of nondeterministic finite automata // Bulletin of the Voronezh State University. Series: System Analysis and Information Technology. 2010. No. 1. P. 5–7. (In Russian.)
Melnikov B.F., Eirich S.N.: An approach to combining the incomplete
branch and bound method and the simulated annealing algorithm // Bulletin of the Voronezh State University. Series: System Analysis and Information Technology. 2010. No. 1. P. 35–38. (In Russian.)
Sigal I.H., Ivanova A.P.: Introduction to applied discrete programming: models and computational algorithms. – Moscow,
Fizmatlit. – 2003. – 240 p. (In Russian.)
Goodman S. E., Hedetniemi S. T. Introduction to the design and analysis of algorithms. N.Y.: McGraw-Hill Publ., 1977. 371 p.
Melnikov B.: Discrete optimization problems – some new heuristic approaches // In: Proceedings – Eighth International Conference on High-Performance Computing in Asia-Pacific Region, Beijing. 2005. P. 73–80.
Melnikov B.F.: Multiheuristic approach to discrete optimization problems // Cybernetics and System Analysis. 2006. No. 3. P. 32– 40. (In Russian.)
Melnikov B., Terentyeva Y.: An approach for obtaining estimation of stability of large communication network taking into account its dependent paths // Cybernetics and Physics. 2022. Vol. 11, No. 3. P. 145–150.
Melnikov B.F., Radionov A.N.: On the choice of strategy in nondeterministic antagonistic games // Programming (Russian Academy of Sciences Ed.). 1998. No. 5. P. 55–62. (In Russian.)
Melnikov B.F.: Heuristics in programming of nondeterministic games // Programming and Computer Software. 2001. Vol. 27, No. 5. P. 277– 288.
Berezovsky B.A., Gnedin A.V.: The task of the best choice. – Moscow, Nauka. – 1984. – 198 p. (In Russian.)
Podinovsky V.V., Nogin V.D.: Pareto-optimal solutions to multicriteria problems. – Мoscow, Fizmatlit. – 2007. – 256 p. (In Russian.)
Melnikov B.F.: On the object-oriented implementation of the branch and bound method for the traveling salesman problem. Part I // Modern Information Technologies and IT Education. 2022. Vol. 18, No. 2. P. 287–299. (In Russian.)
Melnikov B.F.: On the object-oriented implementation of the branch and bound method for the traveling salesman problem. Part II // Modern Information Technologies and IT Education. 2022. Vol. 18, No. 3. P. 644–654. (In Russian.)
Melnikov B.F., Terentyeva Y.Y.: On a graph model for reflectometry problems and some algorithms for their solution. Part III. Approach to test data generation and results of computational experiments // News of higher educational institutions. Volga region. Physical and mathematical sciences. 2022. No. 4 (64). P. 31–41. (In Russian.)
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность IT Congress 2024
ISSN: 2307-8162