The Traveling Salesman Problem (TSP) is possibly the classic discrete optimization problem.
A preview :
Our presentation will pull together material from various sources - see the references below. But most of it will come from [Appl2006], [John1997], [CS153].
The TSP is fairly easy to describe:
Exercise:
Some assumptions and notation for the remainder:
Early history:
Exercise: Find the following 14 cities in Illinois/Indiana on a map and identify the best tour you can:
Bloomington, Clinton, Danville, Decatur, Metamora, Monticello, Mt.Pulaski, Paris, Pekin, Shelbyville, Springfield, Sullivan, Taylorville, Urbana
Exercise: Show how the Knight's tour can be converted into a TSP instance.
TSP's importance in computer science:
Some milestones:
Nearest-neighbor heuristic:
1. V = {1, ..., n-1} // Vertices except for 0. 2. U = {0} // Vertex 0. 3. while V not empty 4. u = most recently added vertex to U 5. Find vertex v in V closest to u 6. Add v to U and remove v from V. 7. endwhile 8. Output vertices in the order they were added to U
Exercise: What is the solution produced by Nearest-Neighbor for the following 4-point Euclidean TSP. Is it optimal?
The Clarke-Wright algorithm:
[Clar1964].
1. Identify a hub vertex h 2. V_{H} = V - {h} 3. for each i,j != h 4. compute savings(i,j) 5. endfor 6. sortlist = Sort vertex pairs in decreasing order of savings 7. while |V_{H}| > 2 8. try vertex pair (i,j) in sortlist order 9. if (i,j) shortcut does not create a cycle and degree(v) ≤ 2 for all v 10. add (i,j) segment to partial tour 11. if degree(i) = 2 12. V_{H} = V_{H} - {i} 13. endif 14. if degree(j) = 2 15. V_{H} = V_{H} - {j} 16. endif 17. endif 18. endwhile 19. Stitch together remaining two vertices and hub into final tour
An approximation algorithm for (Euclidean) TSP that uses the MST: [Rose1977].
Exercise: What is the pre-order for this tree (starting at A)?
→ L takes a shorter route than W (triangle inequality).
What we know about this algorithm:
The Christofides algorithm: [Chri1976].
Exercise: Why?
An improved bound:
Running time:
Constructive vs. local-search heuristics:
1. T = some starting tour // Perhaps by using Christofides. 2. noChange = true 3. repeat 4. T' = makeChangeTo (T) 5. if T' < T 6. T = T' 7. noChange = false 8. endif 9. until noChange 10. return T
1. T = some starting tour 2. noChange = true 3. repeat 4. for all possible edge-pairs in T 5. T' = tour by swapping end points in edge-pair 6. if T' < T 7. T = T' 8. noChange = false 9. break // Quit loop as soon as an improvement is found 10. endif 11. endfor 12. until noChange 13. return T
1. T = some starting tour 2. noChange = true 3. repeat 4. T_{best} = T 5. for all possible edge-pairs in T 6. T' = tour by swapping end points in edge-pair 7. if T' < T_{best} 8. T_{best} = T' 9. noChange = false 10. endif 11. endfor 12. T = T_{best} 13. until noChange 14. return T
Local optima:
Problem landscape:
Climbing out of local minima:
Key ideas:
[Glov1990].
Background:
and low-energy states:
Exercise : Consider the ratio of probabilities above:
Key ideas in simulated annealing: [Kirk1983].
Implementation:
Algorithm: TSPSimulatedAnnealing (points) Input: array of points // Start with any tour, e.g., in input order 1. s = initial tour 0,1,...,n-1 // Record initial tour as best so far. 2. min = cost (s) 3. minTour = s // Pick an initial temperature to allow "mobility" 4. T = selectInitialTemperature() // Iterate "long enough" 5. for i=1 to large-enough-number // Randomly select a neighboring state. 6. s' = randomNextState (s) // If it's better, then jump to it. 7. if cost(s') < cost(s) 8. s = s' // Record best so far: 9. if cost(s') < min 10. min = cost(s') 11. minTour = s' 12. endif 13. else if expCoinFlip (s, s') // Jump to s' even if it's worse. 14. s = s' 15. endif // Else stay in current state. // Decrease temperature. 16. T = newTemperature (T) 17. endfor 18. return minTour Output: best tour found by algorithm
Algorithm: randomNextState (s) Input: a tour s, an array of integers // ... Swap a random pair of points ... Output: a tour
Algorithm: expCoinFlip (s, s') Input: two states s and s' 1. p = exp ( -(cost(s') - cost(s)) / T) 2. u = uniformRandom (0, 1) 3. if u < p 4. return true 5. else 6. return false Output: true (if coinFlip resulted in heads) or false
Temperature issues:
Analysis:
In practice:
Variations:
Our presentation will follow the one in [Vale1997].
First, a definition:
Exercise: What is the difference between the optimal tour and the min-1-tree for this graph?
Held-Karp's idea:
Exercise: What is the difference between the min-1-tree and the optimal tour for the above modified graph G'? What vertex weight for the top-right vertex best closes the gap between the min-1-tree and the optimal tour?
In more detail:
An optimization procedure:
First, a little background on gradient-based optimization:
while not over if gradient < 0 move rightwards else if gradient > 0 move leftwards else stop // gradient = 0 (unlikely in practice, of course) endif endwhile
while not over x = x - α f'(x) endwhileHere, we add a scaling factor α in case f'(x) values are of a different order-of-magnitude:
Back to vertex-weight optimization:
Key ideas:
Note: we will use an artificial depiction of a tour as follows:
This will be used to explain some ideas.
The LK algorithm in more detail:
Performance:
From 1999-2009, Keld Helsgaun [Hels2009], added a number of sophisticated optimizations to the basic LK algorithm:
Key additions to LKH-1:
Let's examine the partitioning idea:
1. repeat // Note: this is a different K than in K-OPT. 2. Pick k centroids. 3. Assign each point to closest centroid. 4. Re-compute the centroid based on assignments. 5. until no change
Iterative partial transcription (IPT):
Given a K-OPT move, is the resulting "tour" a valid tour?
Operations on tour data structures:
Arrays:
→
Can take O(n).
Doubly-linked lists:
Modified splay trees:
Exercise: What is the tour represented by the above tree?
The segment tree:
Performance:
The general idea:
But, first, what is Integer Programming? We'll need some background in linear programming.
Linear programming:
max c_{1}x_{1} + c_{2}x_{2} + ... + c_{n}x_{n} such that a_{11}x_{1} + ... + a_{1n}x_{n} ≤ b_{1} a_{21}x_{1} + ... + a_{2n}x_{n} ≤ b_{2} . . . a_{n1}x_{1} + ... + a_{nn}x_{n} ≤ b_{n} and x_{i} ≥ 0, i=1,...,n x_{i} ε R
max c^{T}x s.t. Ax ≤ b x ≥ 0
max c^{T}x s.t. Ax = b x ≥ 0can be converted to an equivalent one in standard form (with inequality constraints).
Integer programming:
max c^{T}x s.t. Ax ≤ b x ≥ 0 x ε Z
First, let's express TSP as an IP problem:
min Σ_{i,j} c_{i,j} x_{i,j} s.t. Σ_{j} x_{i,j} = 1 // Only one outgoing arc from i Σ_{i} x_{i,j} = 1 // Only one incoming arc at j
You can get multiple cycles.
→
Called sub-tours
Solving the IP problem:
History of applying IP to TSP:
repeat solve LP identify sub-tours (cycles) and add corresponding "|S|-1" constraints. until full-tour found
[WP-1]
Wikipedia entry on TSP.
[WP-1]
Georgia Tech website on TSP.
[Appl2006]
D.L.Applegate, R.E.Bixby, V.Chvatal and W.J.Cook.
The Traveling Salesman Problem, Princeton Univ. Press, 2006.
[Aror1992]
S.Arora, C.Lund, R.Motwani, M.Sudan and M.Szegedy.
Proof verification and hardness of approximation problems.
Proc. Symp. Foundations of Computer Science, 1992, pp.14-23.
[Aror1998]
S.Arora.
Polynomial Time Approximation Schemes for
Euclidean Traveling Salesman and other Geometric Problems.
J.ACM, 45:5, 1998, pp. 753-782.
[Bear1959]
J.Beardwood, J.H.Halton and J.M.Hammersley.
The Shortest Path Through Many Points.
Proc. Cambridge Phil. Soc., 55, 1959, pp.299-327.
[Chan1994]
B.Chandra, H.Karloff and C.Tovey.
New results on the old k-opt algorithm for the
TSP.
5th ACM-SIAM Symp. on Discrete Algorithms, 1994, pp.150-159.
[Clar1964]
G.Clarke and J.W.Wright.
Scheduling of vehicles from a central depot to a number of
delivery points.
Op.Res., 12 ,1964, pp.568-581.
[Chri1976]
N.Christofides.
Worst-case analysis of a new heuristic for the travelling salesman problem.
Report No. 388, GSIA, Carnegie-Mellon University, Pittsburgh, PA, 1976.
[Croe1958]
G.A.Croes.
A method for solving traveling salesman problems.
Op.Res., 6, 1958, pp.791-812.
[Fred1995]
M.L.Fredman, D.S.Johnson, L.A.McGeogh and G.Ostheimer.
Data structures for traveling salesmen.
J.Algorithms, Vol.18, 1995, pp.432-479.
[Glov1990]
F.Glover.
Tabu Search: A Tutorial,
Interfaces, 20:1, 1990, pp.74-94.
[Guti2007]
G.Gutin and A.Yeo.
The Greedy Algorithm for the Symmetric TSP.
Algorithmic Oper. Res., Vol.2, 2007, pp.33--36.
[Held1970]
M.Held and R.M.Karp.
The traveling-salesman problem and minimum spanning
trees.
Op.Res., 18, 1970, pp.1138-1162.
[Hels1998]
K. Helsgaun.
An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic,
DATALOGISKE SKRIFTER (Writings on Computer Science), No. 81, 1998,
Roskilde University.
[Hels2009]
K. Helsgaun.
General k-opt submoves for the Lin-Kernighan TSP heuristic.
Mathematical Programming Computation, 2009.
[John1997]
D.S.Johnson and L.A.McGeoch.
The Traveling Salesman Problem: A Case Study in Local Optimization.
In Aarts, E. H. L.; Lenstra, J. K., Local Search in Combinatorial Optimisation, John Wiley and Sons Ltd, pp. 215¡V310, 1997.
[Karp1972]
R.Karp.
Reducibility among combinatorial problems,
in R. E. Miller and J. W. Thatcher (editors).
, New York: Plenum. pp. 85-103.
[Kirk1983]
S.Kirkpatrick, C.D.Gelatt, and M.P.Vecchi.
Optimization by Simulated Annealing.
Science, 220 1983, pp.671-680.
[Lin1973]
S.Lin and B.W.Kernighan.
An Effective Heuristic Algorithm for the Traveling-
Salesman Problem.
Op.Res., 21, 1973, pp.498-516.
[Mobi1999]
A.Mobius, B.Freisleben, P.Merz and M.Schreiber.
Combinatorial optimization by iterative partial transcription.
Phys.Rev. E, 59:4, 1999, pp.4667-74.
[Rein1991]
G.Reinelt.
TSPLIB ¡X A Traveling Salesman Problem Library.
ORSA J. Comp.,
3:4, 1991, pp. 376-384.
D.J.Rosenkrantz, R.E.Stearns and P.M.Lewis.
An analysis of several heuristics for the traveling salesman
problem.
SIAM J. Computing, Vol.6, 1977, pp.563-581.
[Sahn1976]
S.Sahni and T.Gonzalez. P-complete approximation problems.
J.ACM, Vol.23, 1976, pp.555-565.
[CS153]
R.Simha.
Course notes for CS-153 (Undergraduate algorithms course).
[Vale1997]
C.L.Valenzuela and A.J.Jones.
Estimating the Held-Karp lower bound for the geometric TSP.
European J. Op. Res.,
102:1, 1997, pp.157-175.
Note: The Hilbert curve was an image found on Wiki-commons.