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
|
Roheen Qamar, Baqar Ali Zardari.
© 2025.
18 pages.
|
|
Shugufta Fatima, C. Kishor Kumar Reddy, Akshita Sunerah, Srinath Doss.
© 2025.
34 pages.
|
|
Padmini Mishra.
© 2025.
42 pages.
|
|
Nikita Sharma.
© 2025.
36 pages.
|
|
T. Monika Singh, C. Kishor Kumar Reddy, B. V. Ramana Murthy, Anindya Nag, Srinath Doss.
© 2025.
30 pages.
|
|
C. Kishor Kumar Reddy, Arshita Chintalapalli, Anindya Nag.
© 2025.
30 pages.
|
|
Suryanarayana Murthy Suryanarayana Yamijala, R. S. C. Murthy Chodisetty, Chandresh Chakravorty, K. Pardha Sai.
© 2025.
22 pages.
|
|
|