В компьютерной литературе описано много проблем, которые можно назвать задачами дискретной оптимизации: от шифрования информации в Интернете (включая создание программ для цифровых криптовалют) до поиска групп по интересам в социальных сетях. Часто эти задачи очень сложно решить на компьютере, поэтому их называют «труднорешаемыми».Точнее, сложно описывать возможные подходы к решению этих проблем; при этом программы, основанные на полном переборе вариантов, как правило, программируются просто, но работают значительно медленнее. Почти каждую из этих трудноразрешимых задач можно назвать математической моделью. В то же время как сама модель, так и алгоритмы, предназначенные для ее решения, часто создаваемые для одной предметной области, могут быть также использованы во многих других областях. Примером такой модели является задача коммивояжера. Особенность проблемы в том, что несмотря на относительную простоту её формулировки, поиск оптимального решения (оптимального маршрута) достаточно сложен. Эта задача очень трудна и относится к так называемому классу NP-полных задач. Кроме того, согласно существующей классификации, задача коммивояжера является примером оптимизационной задачи из самого сложного подкласса этого класса. В настоящей работе мы описываем несколько вариантов алгоритмов формирования исходных данных для задачи коммивояжера. После этого мы рассматриваем как классические эвристики, связанные с методом ветвей и границ, так и некоторые дополнения к ним. Далее мы представляем программную реализацию нашей интерпретации алгоритма. В конце статьи мы предлагаем несколько задач для дальнейшего исследования, поэтому статью можно считать описанием проекта для научной работы студентов. (На англ.) С. 41–58.

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.