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.
In this paper, we describe several variants of algorithms for generating source data for the
traveling salesman problem. We consider both the classical heuristics associated with the
branch and bound method, and some added to them. Next, we present a software implementation of our interpretation of the algorithm. At the end of the paper, we formulate
some tasks for further research, so the paper can be a project for students’ scientific work.