Transcription
An Experimental Evaluation of the Best-of-ManyChristofides’ Algorithm for the Traveling SalesmanProblemDavid P. WilliamsonCornell UniversityJoint work with Kyle Genova, Cornell UniversityJuly 14, 2015ISMP 2015Pittsburgh, PA, USA
Kyle will be applying to CS grad schools this coming year.Look for his application!
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The traveling salesman problemTraveling Salesman Problem (TSP)Input: A complete, undirected graph G (V , E ); Edge costs c(i, j) 0 for all e (i, j) E .Goal: Find the min-cost tour that visits each city exactly once.Costs are symmetric (c(i, j) c(j, i)) and obey the triangleinequality (c(i, k) c(i, j) c(j, k)).Asymmetric TSP (ATSP) input has complete directed graph, andc(i, j) may not equal c(j, i).
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The traveling salesman problemFrom Bill Cook, tour of 647 US colleges(www.math.uwaterloo.ca/tsp/college)
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The traveling salesman problemFrom Bill Cook, tour of 647 US colleges(www.math.uwaterloo.ca/tsp/college)
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Approximation AlgorithmsDefinitionAn α-approximation algorithm is a polynomial-time algorithm thatreturns a solution of cost at most α times the cost of an optimalsolution.Long known: A 23 -approximation algorithm due to Christofides(1976). No better approximation algorithm yet known.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Christofides’ algorithmCompute minimum spanning tree (MST) F on G, then compute aminimum-cost perfect matching M on odd-degree vertices of T .“Shortcut” Eulerian traversal in resulting Eulerian graph of F M.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Christofides’ algorithmCompute minimum spanning tree (MST) F on G, then compute aminimum-cost perfect matching M on odd-degree vertices of T .“Shortcut” Eulerian traversal in resulting Eulerian graph of F M.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Christofides’ algorithmCompute minimum spanning tree (MST) F on G, then compute aminimum-cost perfect matching M on odd-degree vertices of T .“Shortcut” Eulerian traversal in resulting Eulerian graph of F M.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Christofides’ algorithmCompute minimum spanning tree (MST) F on G, then compute aminimum-cost perfect matching M on odd-degree vertices of T .“Shortcut” Eulerian traversal in resulting Eulerian graph of F M.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Special casesSome progress in the case of graph TSP:input is a graph G (V , E ), cost c(i, j) is number of edges inshortest path from i to j.Oveis Gharan, Saberi, Singh(2011)32Mömke, Svensson(2011)1.462Mucha(2012)Sebő, Vygen(2012)139 1.44475 1.4
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Special casesAlso progress on s-t path TSP:Usual TSP input plus s, t V , find a min-cost path from s to tvisiting all other nodes in between.Hoogeveen(1991)An, Kleinberg, Shmoys(2012)Sebő(2013)53 1 5 285 1.6Vygen(2015)1.59991.618
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’A central ideaIdea: run Christofides’, but start with tree determined by LPrelaxation of TSP (or s-t path TSP), the Subtour LP.MinXce xee Esubject to:x (δ(v )) 2, v V ,x (δ(S)) 2, S V , S 6 ,0 xe 1, e E ,where δ(S) is the set of all edges with exactly one endpoint in S,Pand x (F ) e F xe .
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The Subtour LPMinXce xee Esubject to:For x feasible for LP,x (δ(v )) 2, v V ,x (δ(S)) 2, S V , S 6 ,0 xe 1, e E .n 1n xin spanning tree polytope{x E : x (E ) n 1, x (E (S)) S 1 S V , S 2},where E (S) is the set of edges with both endpoints in S.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Best-of-Many Christofides’ For Subtour LP soln. x , compute decomposition of n 1n x intoconvex combination of spanning trees F1 , . . . , Fk , thatkn 1 Xx λi χFi ,ni 1where λi 0, ki 1 λi 1, and χF {0, 1} E the characteristicvector of edges in F .PThen run Christofides’ algorithm on each Fi : find matching Mi ,shortcut Fi Mi . Return best tour found.Originally proposed by Oveis Gharan, Saberi, Singh (2011), used inAn, Kleinberg, Shmoys (2012).
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’An alternate perspectiveAn alternate perspective on Best-of-Many Christofides: for SubtourLP soln. x , have an implicit convex combination F1 , . . . , Fk ,kn 1 Xx λi χFi ,ni 1and ability to sample a tree Fi with probability λi . Then runChristofides’ algorithm on Fi , so that expected cost of tree is atmost LP solution, andPr[edge e in sampled tree] xe .Advantage: Don’t need to explicitly construct the convexcombination.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The questionBest-of-Many Christofides’ (BoMC) is provably better thanChristofides’ for s-t path TSP. What about TSP?Is BoMC empirically better than Christofides’?
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The algorithmsWe implement algorithms to do the following: Run the standard Christofides’ algorithm (Christofides 1976);
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The algorithmsWe implement algorithms to do the following: Run the standard Christofides’ algorithm (Christofides 1976); Construct explicit convex combination via column generation(An 2012);
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The algorithmsWe implement algorithms to do the following: Run the standard Christofides’ algorithm (Christofides 1976); Construct explicit convex combination via column generation(An 2012); Construct explicit convex combination via splitting off (Frank2011, Nagamochi, Ibaraki 1997);
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The algorithmsWe implement algorithms to do the following: Run the standard Christofides’ algorithm (Christofides 1976); Construct explicit convex combination via column generation(An 2012); Construct explicit convex combination via splitting off (Frank2011, Nagamochi, Ibaraki 1997); Add sampling scheme SwapRound to both of above; givesnegative correlation properties (Chekuri, Vondrák, Zenklusen2010);
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The algorithmsWe implement algorithms to do the following: Run the standard Christofides’ algorithm (Christofides 1976); Construct explicit convex combination via column generation(An 2012); Construct explicit convex combination via splitting off (Frank2011, Nagamochi, Ibaraki 1997); Add sampling scheme SwapRound to both of above; givesnegative correlation properties (Chekuri, Vondrák, Zenklusen2010); Compute and sample from maximum entropy distribution(Asadpour, Goemans, Madry, Oveis Gharan, Saberi 2010).Code available on github (pointer on the last slide).
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The instancesWe run these algorithms on several types of instances: 59 Euclidean TSPLIB (Reinelt 1991) instances up to 2103vertices; 5 non-Euclidean TSPLIB instances (gr120, si175, si535,pa561, si1032); 39 Euclidean VLSI instances (Rohe) up to 3694 vertices; 9 graph TSP instances (Kunegis 2013) up to 1615 vertices.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Executive summary Standard Christofides’ in general the worst; 9-10% away fromoptimal (similar to results in Johnson and McGeoch 2002).12% away on graph TSP instances (see also Walter andWegmann 2014). BoMC about 3-7% away from optimal on Euclidean instances,2-3% away from optimal for non-Euclidean, 1% for graphTSP instances. Maximum entropy sampling the best, though splitting-off SwapRound also very good.
David P. WilliamsonOutline1. Introduction2. The algorithms3. The instances4. The results5. Some conclusionsExperimental Evaluation of Best-of-Many Christofides’
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Standard Christofides’Use Prim’s algorithm to find MST; if Euclidean instance, first findDelaunay triangulation using Triangle (Shewchuk 1996)Compute matching via Blossom V code of Kolmogorov (2009).Do simple optimization on shortcutting.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Column generationFrom An’s Ph.D. thesis. We compute the Subtour LP solution x using Concorde (Applegate, Bixby, Chvátal, Cook). Then consider:MinXsee Esubject to:XyT se T :e Tn 1 x ,n e e E ,yT 0, T .se 0, e E .Optimal solution is s 0.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Column generationDual is:Maxn 1 X x zen e E esubject to:Xze 0, T ,e Tze 1, e E .Pricing problem is computing max-weight spanning tree on dualsolution ze .
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Column generationBecause convergence to optimal takes a long time, we stop early ifthere isn’t progress in 100 iterations.Early termination for TSPLIB D198
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offConsider Eulerian multigraph represented by Kx for some integerK , graph will be 2K -edge-connected. Lovász (1976) shows that forEulerian multigraphs, vertex v , can split off edges from v : removeedges (u, v ), (v , w ), add edge (u, w ) such that remaining verticesare still 2K -edge-connected.vuw G v
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offConsider Eulerian multigraph represented by Kx for some integerK , graph will be 2K -edge-connected. Lovász (1976) shows that forEulerian multigraphs, vertex v , can split off edges from v : removeedges (u, v ), (v , w ), add edge (u, w ) such that remaining verticesare still 2K -edge-connected.vuw G v
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offConsider Eulerian multigraph represented by Kx for some integerK , graph will be 2K -edge-connected. Lovász (1976) shows that forEulerian multigraphs, vertex v , can split off edges from v : removeedges (u, v ), (v , w ), add edge (u, w ) such that remaining verticesare still 2K -edge-connected.vuw G vNagamochi and Ibaraki (1997) show how to compute a completesplitting off from v in O(nm n2 log n) time.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Splitting offWe split off all vertices except two, then inductively construct acollection of trees by lifting back the split off edges.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’SwapRoundSwapRound (Chekuri, Vondrák, Zenklusen 2010) randomly samplesa spanning tree given an explicit convex combination of trees.For any fixed set A of edges, the edges of the sampled treeappearing in A are negatively correlated; if Xe is the event edge eappears in the tree, then E e AXe YPr[Xe ].e ANegative correlation allows the proof of concentration of measureresults (used by Asadpour et al. for ATSP).
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’SwapRoundSwapRound maintains a single tree (initially the first tree of thecombination), and iteratively calls MergeBasis on the current treeand the next tree in the combination.MergeBasis randomly swaps edges (base exchanges) between thetwo trees until the two are identical.We run 1000 samples per instance, using four threads.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The maximum entropy distributionInfXp(T ) log p(T )T Tsubject to:Xp(T ) T :e TXn 1 x ,n e e E ,p(T ) 1T Tp(T ) 0, T .Asadpour et al. show that there exist γe such that the optimalPp(T ) exp ( e T γe ), and give an algorithm to approximatelycalculate the γ. They also give a poly-time algorithm to sample atree T given the γ.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The maximum entropy distributionWe implemented the algorithms of Asadpour et al. but alsoalgorithms in a code of Oveis Gharan. The latter were faster inpractice.As with SwapRound, we compute 1000 samples for each instancein parallel with four threads.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The experimentsThe algorithms were implemented in C , run on a machine witha 4.00Ghz Intel i7-875-K processor with 8GB DDR3 memory.We run these algorithms on several types of instances: 59 Euclidean TSPLIB (Reinelt 1991) instances up to 2103vertices (avg. 524); 5 non-Euclidean TSPLIB instances (gr120, si175, si535,pa561, si1032); 39 Euclidean VLSI instances (Rohe) up to 3694 vertices (avg.1473); 9 graph TSP instances (Kunegis 2013) up to 1615 vertices(avg. 363).
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The resultsStdColGenBestAve4.03% 6.44%7.00% 8.51%2.73% 4.41%0.57% 1.37%TSPLIB (E)VLSITSPLIB (N)Graph9.56%9.73%5.40%12.43%TSPLIB (E)VLSITSPLIB (N)GraphMaxEntBestAve3.19% 6.12%5.47% 7.61%2.12% 3.99%0.31% 1.23%ColGen SRBestAve3.45% 6.24%6.40% 8.33%2.22% 4.08%0.39% 1.29%SplitBestAve5.23% 6.27%6.60% 7.64%2.92% 3.77%0.88% 1.77%Costs given as percentages in excess of optimal.Split SRBestAve3.60% 6.02%5.48% 7.52%1.99% 3.82%0.33% 1.20%
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The resultsStandard Christofides MST (Rohe VLSI instance XQF131)Splitting off SwapRound
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The resultsBoMC yields more vertices in the tree of degree two.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The resultsSo while the tree costs more (as percentage of optimal tour).TSPLIB (E)VLSITSPLIB 99.36%98.23%
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’The results.the matching costs much less.TSPLIB (E)VLSITSPLIB .67%5.20%CG Split10.65%12.78%8.77%4.34%Sp SR10.41%12.70%8.56%4.49%
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’ConclusionQ: Are there empirical reasons to think BoMC might be provablybetter than Christofides’ algorithm?
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’ConclusionQ: Are there empirical reasons to think BoMC might be provablybetter than Christofides’ algorithm?A: Yes.Maximum entropy sampling, or splitting off with SwapRound seemlike the best candidates.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’ConclusionHowever, we have to be careful, as the following, very recent,example of Schalekamp and van Zuylen shows.011201110101112121
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’ConclusionsSo it seems that randomization, or at least, careful construction ofthe convex combination is needed.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’ConclusionsSo it seems that randomization, or at least, careful construction ofthe convex combination is needed.Vygen (2015) also uses careful construction to improve s-t pathTSP from 1.6 to 1.5999.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’ConclusionsSo it seems that randomization, or at least, careful construction ofthe convex combination is needed.Vygen (2015) also uses careful construction to improve s-t pathTSP from 1.6 to 1.5999.If we want to use the best sample from Max Entropy orSwapRound, then might need to prove some tail bounds.
David P. WilliamsonExperimental Evaluation of Best-of-Many Christofides’Thanks for your attention.Paper available athttp://arxiv.org/abs/1506.07776.Code available ck? Contact me atdpw@cs.cornell.edu.
David P. Williamson Experimental Evaluation of Best-of-Many Christofides' Acentralidea Idea: runChristofides',butstartwithtreedeterminedbyLP
