Newsgroups: sci.math,sci.op-research From: david@research.att.com (David Applegate) Subject: Re: TSP CONTEST - Winners Writeups Date: Tue, 28 Mar 1995 05:22:05 GMT Keywords: traveling salesman problem, TSP, asymmetric, ATSP These problems (47, 99, 110, and 111 city asymmetric traveling salesman problems) are not beyond the scope of state-of-the-art TSP algorithms. I used our linear-programming, cutting-plane branch-and-bound code to optimally solve them. The code solves symmetric problems, so I used a reduction (splitting each node into an input and output half, adding a 0-cost edge between the two halves, and forcing that edge to be in the solution). The code was designed with large, euclidean problems in mind (the largest we've solved to optimality had 7,397 cities), but handles arbitrary symmetric distance matrices. In our experience, the hard part of solving a TSP to optimality is the lower bound, not the upper bound, and the asymmetry doesn't cause very many problems for the lower bound. However, the asymmetry does cause difficulties for the best, Lin-Kernighan based upper bound heuristics, since they make swaps which reverse segments of the tour. For hard problems, this is troublesome, since a good upper bound helps the lower bound by allowing you to eliminate more edges and also prune the search tree. For these relatively easy problems, I started without an upper bound, which meant that it had to branch to an integral solution before it could do any pruning at all. The optimal solutions (the solutions for the 47 and 99 city problems have been already reported here by Bruno W. Repetto) (running times are on an SGI Challenge with a 150Mhz R4400 processor): 47 cities: Length 45750, found and proved in 68 seconds: 39 31 25 43 18 4 20 42 5 15 12 17 33 21 35 0 14 37 13 27 6 46 22 41 38 11 29 40 32 2 1 16 23 26 10 8 19 36 28 9 34 3 45 44 7 24 30 99 cities: Length 78448, found and proved in 471 seconds: 63 24 34 76 72 41 43 68 19 57 87 65 8 12 94 14 16 83 11 58 77 96 61 74 33 22 98 38 69 70 53 1 54 40 35 78 73 60 2 20 6 29 18 56 42 82 67 88 80 52 50 30 93 95 17 55 47 21 62 5 27 97 91 4 49 51 75 26 31 85 90 13 66 71 92 89 23 79 37 10 32 9 45 81 36 59 7 44 86 39 0 3 64 15 48 84 46 25 28 110 cities: Length 87045, found and proved in 7202 seconds: 107 58 97 84 8 78 19 42 96 88 29 32 100 65 4 51 82 73 30 13 46 1 3 71 104 68 26 54 91 75 33 92 47 11 28 61 64 15 14 37 56 27 43 2 69 25 10 34 20 35 87 76 57 12 79 67 52 77 60 98 5 39 85 0 103 105 53 99 74 81 86 94 38 101 93 16 40 55 44 7 70 18 48 62 83 106 59 90 63 41 22 23 50 21 24 72 9 80 36 108 45 6 89 17 109 31 95 49 66 102 111 cities: Length 85879, found and proved in 1406 seconds: 80 27 106 22 65 109 44 42 88 58 57 93 69 6 50 8 1 95 100 14 84 29 34 32 15 108 68 91 79 89 72 13 90 53 49 21 52 60 7 37 107 12 25 62 97 46 45 67 64 20 86 26 33 78 48 43 103 63 18 75 36 16 55 2 92 81 73 76 38 40 41 51 47 85 83 94 56 9 102 61 35 59 11 17 87 70 39 24 4 99 19 5 0 98 77 71 28 74 3 101 82 54 110 23 66 105 96 10 30 104 31 In article , Bruno W. Repetto wrote: >Chad: You wrote: > >> In article you write: >> > >> >The 47 city problem is not too hard for the state-of-the-art TSP algorithms. >> >:-) I have been able to prove that the solution displayed above for this >> >problem is indeed optimal. >> > >> >Bruno W. Repetto >> >br0w+@andrew.cmu.edu >> >> you are correct, the 47 is not difficult to solve, it is the 100~ cities that >> are giving me trouble, but i think there is a relaxation that can do them >> in just like standard symmetric relaxations do geometric problems in. > >I beg to differ. For problems this large, relaxations more specific to the >ATSPs are required. STSP relaxations are experimentally doomed to be >ineffective. I have a branch-and-bound code that uses Balas' restricted >Lagrangean approach, with Fischetti and Toth's r-arborescence relaxation. >I also use some so-called CAT inequalities and all the "D(k)" inequalities I >can find. These apply only to the Asymmetric TSP. > >> Have you tried the 100~ city problems? Also do you know of "tsp_solve?" > >I haven't had the time to try tsp_solve... I will try it "soon" :-) > >I responded to the immediate request for the optimal solution of the 47-city >problem, and wanted to release the solutions of the larger problems later this >week or early next week. But the masses are restless :-) > >This is the solution for the 99-city problem. It is optimal. I am working on >the 110- and 111-city problems as I write this. Wish me luck on those. It >took a long time to prove the optimality of the solution below... > > >Optimal solution cost: 78448 > > >The optimal sequence is: > 63 24 34 76 72 41 43 68 19 > 57 87 65 8 12 94 14 16 83 11 > 58 77 96 61 74 33 22 98 38 69 > 70 53 1 54 40 35 78 73 60 2 > 20 6 29 18 56 42 82 67 88 80 > 52 50 30 93 95 17 55 47 21 62 > 5 27 97 91 4 49 51 75 26 31 > 85 90 13 66 71 92 89 23 79 37 > 10 32 9 45 81 36 59 7 44 86 > 39 0 3 64 15 48 84 46 25 28 > >> -skito >> >> -- >> here i am >> here i am >> waiting to hold >> churritz@cts.com This Mortal Coil -- you > >Bruno W. Repetto >br0w+andrew.cmu.edu >