• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Branch-and-bound algorithm for Symmetric Travelling Salesman Problem
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 15, 2026
Immunity to Chaos: How Personal Resources Help Us Cope with the Challenges of a Turbulent World
International conflicts, crises and digital overload—the modern world puts our minds to the test every day. Traditional psychology often focuses on the consequences: anxiety, depression, and psychosomatic disorders. But what if we looked at the problem differently—through the lens of the resources that prevent us from breaking down? Psychological immunity is precisely this set of resources. Alena Zolotareva and her group, Psychological Immunity as a Resource for Positive Functioning, are developing an integrative model of this phenomenon, adapting diagnostic tools and preparing for large-scale empirical research. Why do psychologists need to collaborate with medical professionals, and how could their research transform preventive care in clinics and corporations?
September 11, 2026
How to Assess Students Knowledge in the Age of AI
A researcher at HSE University has proposed a flowchart to help lecturers decide how to assess students who use artificial intelligence. It shows where the use of AI should be restricted and where it can be incorporated into the learning process. The article has been published in IT Professional.
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Branch-and-bound algorithm for Symmetric Travelling Salesman Problem

P. 311–322.
Alexey Nikolaev, Mikhail Batsyn

In this paper a branch-and-bound algorithm for the Symmetric Travelling Salesman Problem (STSP) is presented. The algorithm is based on the 1-tree Lagrangian relaxation. A new branching strategy is suggested in which the algorithm branches on the 1-tree edge belonging to the vertex with maximum degree in the 1-tree and having the maximum tolerance. This strategy is compared with} branching on the shortest edge and the so-called strong branching, which is the branching on the edge with maximum tolerance also applied by Held & Karp (1971). The computational experiments show that {proposed} branching strategy provides better results on TSPlib benchmark instances.

Language: English
Full text
DOI
Text on another site
Keywords: Traveling Salesman Problem1-treeBranch-and-bound algorithm

In book

Combinatorial Algorithms. 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018. Lecture Notes in Computer Science
Combinatorial Algorithms. 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018. Lecture Notes in Computer Science
Vol. 10979. , Springer, 2018.
Similar publications
Коррeляция сложности и времени решения TSP
Головешкин В. А., Zhukova G., Ulyanov M. et al., Системы компьютерной математики и их приложения 2017 № 18 С. 136–138
В докладе рассматривается статистическая зависимость числа порожденных вершин дерева решений и физического времени работы программной реализации метода ветвей и границ для задачи коммивояжера (TSP). На основе результатов вычислительного эксперимента получено приближенное соотношение между числом  порожденных вершин (сложность индивидуальной TSP) и физическим временем. Предлагается использовать это эмпирическое соотношение для прогнозирования времени работы программы, решающей TSP с числом «городов» больше 40. ...
Added: March 22, 2020
Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра
Ulyanov M., Fomichev M., Информационные технологии 2019 Т. 25 № 10 С. 590–595
The algorithm that implements the Branch and Bound method for solving the Traveling Salesman Problem is one of the common exact algorithms for solving it. Metaheuristic algorithms for solving this problem do not guarantee obtaining an exact solution, however they work "quickly". In order to reduce the nodes number of the generated decision tree in ...
Added: February 16, 2020
Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности
Zhukova G., Ulyanov M., Fomichev M., Автоматика и телемеханика 2019 № 11 С. 155–172
We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin-Kernighan-Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show ...
Added: November 10, 2019
Implementation and Use of Coarse-grained Parallel Branch-and-bound in Everest Distributed Environment
Voloshinov V., Smirnov S., Sukhoroslov O. V., Procedia Computer Science 2017 Vol. 108 P. 1532–1541
This paper examines the coarse-grained approach to parallelization of the branch-and-bound (B&B) algorithm in a distributed computing environment. This approach is based on preliminary decomposition of a feasible domain of mixed-integer programming problem into a set of subproblems. The produced subproblems are solved in parallel by a distributed pool of standalone B&B solvers. The incumbent ...
Added: August 30, 2018
Some approaches to solving the NP-hard Mixed Chinese Postman Problem
Maria Gordenko, Sergey Avdoshin, , in: Материалы пятой международной конференции «Актуальные проблемы системной и программной инженерии», сборник научных трудовVol. 1989: CEUR Workshop Proceedings.: M.: HSE, 2017. P. 272–290.
The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which ...
Added: November 18, 2017
The Mixed Chinese Postman Problem
M.K. Gordenko, S.M. Avdoshin, Proceedings of the Institute for System Programming of the RAS 2017 Vol. 29 No. 4 P. 107–122
The routing problems are important for logistic and transport sphere. Basically, the routing problems related to determining the optimal set of routes in the multigraph. The Chinese postman problem (CPP) is a special case of the routing problem, which has many potential applications. We propose to solve the MCPP (special NP-hard case of CPP, which ...
Added: September 27, 2017
Использование квантильных коэффициентов асимметрии и эксцесса для оценки сложности решения задачи коммивояжера
Fomichev M., Ulyanov M., Головешкин В. А. et al., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131–137
It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the ...
Added: August 19, 2017
Transformation of the Mixed Chinese Postman Problem in multigraph into the Asymmetric Travelling Salesman Problem
Maria K. Gordenko, Avdoshin S. M., International Journal of Open Information Technologies 2017 Vol. 5 No. 6 P. 6–11
The Mixed Chinese Postman Problem (MCPP) is to find a minimum shortest tour of given graph or multigraph traversed each edge or arc at least once. The problem is NP-hard. However, mixed case of the problem has many potentially useful applications, including delivering of something, robot exploration, web site usability, etc. In this article, we ...
Added: June 1, 2017
Распределение логарифма сложности индивидуальных задач коммивояжера при фиксированной длине входа/ Probability distribution of the complexity of the individual traveling salesman problem (fixed number of nodes)
Головешкин В. А., Жукова Г. Н., Ulyanov M. et al., В кн.: CEUR Workshop ProceedingsVol. 1761: SITITO 2016. Modern Information Technologies and IT-Education. Selected Papers of the XI International Scientific-Practical Conference Modern Information Technologies and IT-Education (SITITO 2016). Moscow, Russia, November 25-26, 2016.: CEUR Workshop Proceedings, 2016. С. 304–310.
It is shown that the logarithm of the complexity (number of nodes in the decision tree of a branch and bound algorithm) of the individual traveling salesman problem is approximately normally distributed. We use a linear regression model (logarithm of the complexity — standard normal distribution) to estimate parameters of normal distribution, which fit the ...
Added: March 30, 2017
Анализ точности решения задачи коммивояжера с помощью «антижадного» алгоритма
Chusovliankin A., Morozenko V. V., Вестник Пермского университета. Серия: Математика. Механика. Информатика 2016 Т. 4 № 35 С. 68–75
In this paper the new "anti-greedy" algorithm for the Traveling Salesman Problem is under investigation. The idea of "anti-greedy" algorithm is consequent elimination of the longest edges from graph according to two rules: every node of the graph should have two incident edges as a minimum; the graph should not have cycles with less than ...
Added: January 23, 2017
Resource characteristics of ways to organize a decision tree in the branch-andboundmethod for the traveling salesmen problem
Ulyanov M.V., Fomichev M.I., Business Informatics 2015 No. 4 (34) P. 38–46
The resource efficiency of different implementations of the branch-and-bound method for the classical traveling salesman problem depends, inter alia, on ways to organize a search decision tree generated by this method. The classic «time-memory» dilemma is realized herein either by an option of storing reduced matrices at the points of the decision tree, which leads ...
Added: November 5, 2016
The Theory of Set Tolerances
Jäger G., Goldengorin B. I., Pardalos P. M., , in: Learning and Intelligent Optimization. 8th International Conference, Lion 8, Gainesville, FL, USA, February 16-21, 2014. Revised Selected PapersVol. 8426.: Springer, 2014. P. 362–377.
The theory of single upper and lower tolerances for combinatorial minimization problems has been formalized in 2005 for the three types of cost functions sum, product and maximum, and since then shown to be rather useful in creating heuristics and exact algorithms for the Traveling Salesman Problem and related problems. In this paper for these ...
Added: October 26, 2014
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit