В литературе описано очень много задач, которые могут быть названы задачами дискретной оптимизации: от шифровки информации в Интернете (включая создание программ для криптовалют) до поиска групп <<по интересам>> в социальных сетях. Часто эти задачи очень сложны для решения на компьютере, откуда и идёт их название <<труднорешаемые>>. Точнее, сложны для решения (описания алгоритмов, программирования) возможные подходы к быстрому решению этих задач, переборное же решение, как правило, программируется просто, но работает соответствующая программа гораздо медленнее. Практически каждую из таких труднорешаемых задач можно назвать математической моделью. При этом часто и сама модель, и алгоритмы, предназначенные для её решения, создаются для одной предметной области, но могут найти применение и во многих других областях. Примером такой модели является задача коммивояжёра. Особенностью задачи является то, что при относительной простоте её постановки нахождение оптимального решения (оптимального маршрута) является весьма сложным и относится к так называемому классу NP-полных проблем. Более того, согласно имеющейся классификации, задача коммивояжёра является примером оптимизационной проблемы, входящей в самый сложный подкласс этого класса. Однако основной предмет статьи – это не задача, а метод её решения, метод ветвей и границ. Он состоит из нескольких связанных между собой эвристик, и в монографической литературе подобная мультиэвристичость метода ветвей и границ ранее отмечена, по-видимому, не была: разработчики алгоритмов и программ это должны были понимать сами. При этом сам метод может быть применён с небольшими изменениями и ко многим другим задачам дискретной оптимизации. Итак, классический вариант метода ветвей и границ – основной предмет настоящей статьи, но почти столь же важен и второй её предмет – задача коммивояжёра, тоже в классической её постановке. Речь идёт о применении метода ветвей и границ при решении задачи коммивояжёра, причём в отношении этого применения также можно употребить прилагательное <<классическое>>. Однако в дополнение к классической версии этой реализации мы рассматриваем новые эвристики, связанные с необходимостью разработки алгоритмов реального времени. C. 21-44.

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 solution, 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