IRMA-International.org: Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

The Traveling Salesman Problem: Network Properties, Convex Quadratic Formulation, and Solution

The Traveling Salesman Problem: Network Properties, Convex Quadratic Formulation, and Solution
View Sample PDF
Author(s): Elias Munapo (North-West University, South Africa)
Copyright: 2021
Pages: 22
Source title: Research Advancements in Smart Technology, Optimization, and Renewable Energy
Source Author(s)/Editor(s): Pandian Vasant (University of Technology Petronas, Malaysia), Gerhard Weber (Poznan University of Technology, Poland) and Wonsiri Punurai (Mahidol University, Thailand)
DOI: 10.4018/978-1-7998-3970-5.ch006

Purchase

View The Traveling Salesman Problem: Network Properties, Convex Quadratic Formulation, and Solution on the publisher's website for pricing and purchasing information.

Abstract

The chapter presents a traveling salesman problem, its network properties, convex quadratic formulation, and the solution. In this chapter, it is shown that adding or subtracting a constant to all arcs with special features in a traveling salesman problem (TSP) network model does not change an optimal solution of the TSP. It is also shown that adding or subtracting a constant to all arcs emanating from the same node in a TSP network does not change the TSP optimal solution. In addition, a minimal spanning tree is used to detect sub-tours, and then sub-tour elimination constraints are generated. A convex quadratic program is constructed from the formulated linear integer model of the TSP network. Interior point algorithms are then applied to solve the TSP in polynomial time.

Related Content

Junichiro Hayano, Emi Yuda. © 2021. 15 pages.
Anna Karagianni, Vasiliki Geropanta, Panagiotis Parthenios, Riccardo Porreca, Sofia Mavroudi, Antonios Vogiatzis, Lais-Ioanna Margiori, Christos Mpaknis, Eleutheria Papadosifou, Asimina Ioanna Sampani. © 2021. 21 pages.
Elias Munapo. © 2021. 16 pages.
Elias Munapo, Olusegun Sunday Ewemooje. © 2021. 16 pages.
Zakhid Godzhaev, Sergey Senkevich, Viktor Kuzmin, Izzet Melikov. © 2021. 19 pages.
Elias Munapo. © 2021. 22 pages.
Diriba Kajela Geleta, Mukhdeep Singh Manshahia. © 2021. 39 pages.
Body Bottom