Traveling Salesman Problem

Optimization · Axiom Academy

LESSON Traveling Salesman Problem (TSP) Understanding one of the most famous optimization problems in computer science 1. Problem Definition and Visualization The TSP seeks to find the shortest Hamiltonian cycle in a complete weighted graph. Given n cities, a salesman must visit each city exactly once and return to the starting point, minimizing total travel distance. 2. Integer Programming Formulation The TSP can be formulated as an Integer Programming (IP) problem using binary decision variables. The key challenge is preventing subtours - cycles that don't include all cities. 1. Each city must be exited exactly once: 2. Each city must be entered exactly once: 3. Subtour elimination (Miller-Tucker-Zemlin formulation): TSP is NP-hard, meaning no known polynomial-time algorithm can solve all instances optimally. The number of possible tours grows factorially with the number of cities. 4. Approximation Algorithms and Bounds Since exact algorithms are computationally expensive, several approximation algorithms provide near-optimal solutions in polynomial time. Nearest Neighbor: Start at any city, repeatedly visit the nearest unvisited city 2-Approximation (Christofides): For metric TSP, guarantees solution within 1.5 × optimal Local Search (2-opt): Iteratively improve tour by swapping edges MST Bound: Optimal tour ≥ weight of minimum spanning tree LP Relaxation: Relax x ij ∈ 0,1 to 0 ≤ x ij ≤ 1 5. Comparing Different Solutions

This is the written version of the interactive lesson above. See the full Optimization course.