The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
The Traveling Salesman Problem: Network Properties, Convex Quadratic Formulation, and Solution
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
|
Bhargav Naidu Matcha, Sivakumar Sivanesan, K. C. Ng, Se Yong Eh Noum, Aman Sharma.
© 2023.
60 pages.
|
|
Lavanya Sendhilvel, Kush Diwakar Desai, Simran Adake, Rachit Bisaria, Hemang Ghanshyambhai Vekariya.
© 2023.
15 pages.
|
|
Jayanthi Ganapathy, Purushothaman R., Ramya M., Joselyn Diana C..
© 2023.
14 pages.
|
|
Prince Rajak, Anjali Sagar Jangde, Govind P. Gupta.
© 2023.
14 pages.
|
|
Mustafa Eren Akpınar.
© 2023.
9 pages.
|
|
Sreekantha Desai Karanam, Krithin M., R. V. Kulkarni.
© 2023.
34 pages.
|
|
Omprakash Nayak, Tejaswini Pallapothala, Govind P. Gupta.
© 2023.
19 pages.
|
|
|