How to solve the traveling salesman problem?
In discussing three of my notes about AI, only one person dared to say that he has intellect, “but” a whole bunch of “teachers” appeared who began to teach me how to play chess, and how to solve pereboro problems. Even “linguists” came to light who said that complete search and brute force are “complete synonyms” and that for complete searching it is necessary to look for a solution to the traveling salesman problem in the same idiotic way with factorial complexity. Their logic is clear: “there is power — mind is not necessary”, but if it is still “to move a gyrus,” it becomes clear that FULL brute force is not necessarily a BLAST force, but it could well be a CLEVER force! So we will solve the problem completely by brute force, not forgetting that this is a very smart, subtle, complex algorithm. More precisely, a set of algorithms that pass each other the task "along the chain."
A bit of history. In 2001, the task for 15112 nodes was solved, while the processor time in terms of the 500 MHz Alpha processor was more than 22 years, in 2004 the optimal tour was found for the graph at 24978 nodes (88 years), in 2005 - for 33810 nodes (15 years), in 2006 - for 85,900 knots (136 years). That's all for now. Moreover, strictly speaking, none of the currently known solutions can be considered as such, since the distances between the nodes are rounded to integers, i.e. are calculated approximately. So, for the eil101 graph, the error in determining the length of the best-known tour is about 2%, ho14473 - 1%, lrb744710 - almost 6%, etc. What kind of “exact” solution can we talk about with such terrible mistakes in determining the length of the tour? An even more spectacular example is the World TSP at 1904711 nodes, if the given GEO coordinates are considered to be EUC coordinates, i.e. perform the calculation not on the "globe", but on the "world map". In this case, the rounding error will be more than 10,000%!
Of course, this “petty scam” is not by chance, because it allows you to reduce the computation time, and not just to reduce it, but to reduce it to an UNIMENSIVE number of times! After all, when calculating a tour of length L, any solution found in the range (L-1, L-0.5) reduces the length of the tour by one unit at once, and when searching for this solution, another abyss of options in the range (L-0.5, L) is excluded from consideration. In addition, the number of such "exact" solutions increases with an increase in the number of nodes in the graph. For example, for the graph wi29 there is only one exact solution, and for eil51 there are at least three. For the graph lrb744710, with an average fin length of the best-known tour of less than 2.2 (!), The number of “exact” solutions is probably many billions. In a word, the search for truly exact solutions of problems for such graphs would not require decades, but many thousands of years of CPU time.
Of the whole variety of algorithms, we will consider only those that are based on the modification of the current round, i.e. Our approach is very similar to the classic Lin-Kernighan-Johnson method, like its LKH variant. However, there is a major difference: we use it to find not only an approximate, but also an exact solution. All the tools for this are already available, it remains only to throw away the "mutations" and all the other "ideas from tab search and evolutionary computing", replacing them (at least) with cascade recursion. After all, any accelerating heuristics at this stage only translates the problem from the exact category into approximate ones! We need it?
')
For a detailed check of all the concepts of our approach, we will conduct a large-scale experiment: we will re-solve all known problems, solved and not solved at the moment, including tasks from DIMACS TSP Challenge, and much more difficult to process graphs with hierarchical clustering of our own production, and uniformly random and all the rest. The result was a set of 395 traveling salesman tasks for graphs from 3 to 123456789 nodes.
The algorithm of the lowest possible modification of the tour by replacing two edges (2-opt) is elementary (two edges are removed from the tour, then the resulting chains are again connected to the tour with opposite ends), but very effective - this is the main “workhorse” with a speed modification of the tour - namely it falls the bulk of the fall of the beta border: up to 90% or more. Other algorithms of atomic modification (for example, the “double bridge”, which changes the edges according to the 4-opt scheme), are too expensive and are practically not used as almost useless.
So, we have a graph for which we must find the best tour. We don’t yet know anything about the graph itself and the current tour: the tour is probably optimal (such “miracles” are sometimes found - for example, in graph pr2392, nodes are carefully defined in such a sequence that, connecting the ribs to the second with the second, third, ... the last with the first we just get the best tour). Probably, the error is hundredths of a percent (if, for example, we try to improve the best-known solution for the graph w1904711), perhaps - many thousands of percent (say, the error for the same w1904711 at the start is more than 50,000%) - nothing about the algorithm is known. Therefore, he “assumes the worst,” and the main task of the speed algorithm is to “drop” the beta border as quickly as possible and as low as possible. In this case, it is highly desirable to consider not all the edges of the graph (which are still in the same w1904711 several trillion), but only a very small part of them, but exactly the one that allows us to reduce the beta border. Recall that we also have no information about the edges - they can even be given in tabular form. So are there any criteria for choosing the "right" edges? There are such criteria!
At the start, when loading the source data, we count the length of the current round and, dividing it by the number of nodes of the graph, we obtain the average edge length. Thus, each considered edge of the tour may be less, more, much more than this current average length. It is this information that controls the search: the longer the edge is, the more carefully it is considered: as the edge length increases by every 5% (actually, we have a little more - by 1/16) the depth of consideration (that is, the number of edges of the tour, starting with the current one, which verifies the possibility of atomic changes tour) doubles. However, short edges (in our case, these are edges of medium length and less) are considered only to the minimum depth, which is determined by the current iteration (the stage of finding a solution by any algorithm for all edges of a tour), and in general can be zero. In fact, this is the division of the original graph into subtasks, but the division is dynamic, in fact the elements of the group belong to one section of the current tour.
What does this give? A lot of things! With this approach, short edges at the lower iterations are almost not considered, i.e. the algorithm is not distracted by the “triviality”, and only those options that can give a serious decrease in the beta border look. With each solution found, the average length of the edge decreases, therefore, some edges that were previously considered “short” go into the category of “long” and are drawn into the search. On the contrary, the transition to the next iteration does not depend on the length of the tour, and is determined by the ratio of the number of solutions found during the iteration to the number of nodes of the graph. The meaning is obvious: there is no need to “call for help from the elders” while things are going well. Moreover, if the ratio is very high (tens of percent), it means that the tour managed to be well shattered, and it makes sense to return control to younger (faster) iterations, since the probability of their successful work is very high.
Generally speaking, the actually existing high-speed algorithm works about 10-100 times faster than the one just described, since there are many technical nuances when searching for a solution. We list the most important:
The lion's share of the performance provides the so-called "dobor". After the end of each iteration, if at the same time at least one solution was found, it is repeated, but only for new edges appearing at this iteration. There are usually very few such edges, but they have not yet been considered, and the probability of new solutions among them is quite high. As a result, the “dobor” is performed many times faster, and its efficiency often even exceeds the efficiency of the main iteration. Thus, each iteration reduces the beta border approximately twice as strong, and almost all of its decrease (90% or more) falls on the 2-3 lowest iterations, which significantly speeds up the passage of all other iterations. The program “dobor”, of course, is implemented within the framework of one iteration, which ends not after considering all the ribs of the tour, but after all of them, including the newly appeared ones, receive the status “examined”.
The concept of “minimum base depth” has been introduced (we have 64 edges) - this means that the high-speed algorithm does not have the right to finish the work, even if there is a complete failure to find solutions, until all edges are considered to this minimum depth. Such an approach practically guarantees that the high-speed algorithm will not pass the tour to the next processor with an error of hundreds and thousands of percent. For graphs with large errors in the starting tour, this minimum depth can grow “naturally” (if the iterations succeed in finding quite a lot of improvements in the tour) - I have seen the depth of 1024, and even 8192 (never seen again), but this is for graphs "millionaires." In any case, even such a depth is negligible compared to the number of nodes in the graph, so the operation time of the speed algorithm grows almost linearly in the number of nodes, which confirms the experiment.
Introduced the concept of "absolute edge". If for any edge the depth of calculation is half the nodes of the graph or more, the edge is calculated completely, to the full depth, and is marked as “absolute”, which will not be considered on any of their subsequent iterations of the speed search. For some types of graphs, this technique makes it possible to reduce the search time for a solution by several times.
At an ultra-small depth calculation of the current edge (up to 16), we only look at “turning the chain”, then some speed versions from the 3-opt series are connected, and at a depth of 64 (the minimum required depth) more “heavy” atomic algorithms. This reduces the running time of the speed algorithm by about half.
When processing “superlong” edges (with a length that is 8 or more times longer than the average), the decision to change the tour is made only with a decrease in the length of this particular edge, and not less than 1%. This not only shortens the search time at this iteration, minimizing “mouse fuss” on long edges, but also often noticeably drops the beta border, thus accelerating all other iterations.
There are many other nuances of implementation: limiting the difference in depth of calculating long and short edges, incrementing the length of the edge when choosing the depth to avoid unpleasant interference caused by rounding to the whole (sometimes it accelerates the calculation tenfold!), Technology for changing the basic depth of calculation between iterations, etc.
The experiment showed that the high-speed algorithm (which, as a rule, considers not all edges, sometimes much less than 1%) gives quite satisfactory results, suitable even for practical use. Beta-border with any size (usually it is 3-5 thousand percent of error) drops to 10-20%, rarely higher, often lower. The efficiency of the algorithm for super-large graphs has nothing to compare with: no program known to us can even begin calculating with hundreds of thousands of nodes (at least on a regular PC). In other words, we do not consider it necessary to further improve the speed algorithm. In the end, it is possible to use any heuristic algorithm you like, and its result can be “fed” to ours as input data. What we did when calculating the solution without rounding, substituting the “optimal” tour from TSPLIB as the initial one. Even in this case, the bulk of the solutions found also fall on the high-speed algorithm.
Well, enough, perhaps. It seems that there will also be 3-4 notes here, but how can I write them when I have so much spoiled karma that I can post no more than one note per week in this unfortunate “Recovery Mode”? O-ho-ho ...
A bit of history. In 2001, the task for 15112 nodes was solved, while the processor time in terms of the 500 MHz Alpha processor was more than 22 years, in 2004 the optimal tour was found for the graph at 24978 nodes (88 years), in 2005 - for 33810 nodes (15 years), in 2006 - for 85,900 knots (136 years). That's all for now. Moreover, strictly speaking, none of the currently known solutions can be considered as such, since the distances between the nodes are rounded to integers, i.e. are calculated approximately. So, for the eil101 graph, the error in determining the length of the best-known tour is about 2%, ho14473 - 1%, lrb744710 - almost 6%, etc. What kind of “exact” solution can we talk about with such terrible mistakes in determining the length of the tour? An even more spectacular example is the World TSP at 1904711 nodes, if the given GEO coordinates are considered to be EUC coordinates, i.e. perform the calculation not on the "globe", but on the "world map". In this case, the rounding error will be more than 10,000%!
Of course, this “petty scam” is not by chance, because it allows you to reduce the computation time, and not just to reduce it, but to reduce it to an UNIMENSIVE number of times! After all, when calculating a tour of length L, any solution found in the range (L-1, L-0.5) reduces the length of the tour by one unit at once, and when searching for this solution, another abyss of options in the range (L-0.5, L) is excluded from consideration. In addition, the number of such "exact" solutions increases with an increase in the number of nodes in the graph. For example, for the graph wi29 there is only one exact solution, and for eil51 there are at least three. For the graph lrb744710, with an average fin length of the best-known tour of less than 2.2 (!), The number of “exact” solutions is probably many billions. In a word, the search for truly exact solutions of problems for such graphs would not require decades, but many thousands of years of CPU time.
Formulation of the problem
- The traveling salesman’s task will be solved in the form of a search for Hamiltonian cycles (a closed route including exactly each vertex of the graph once), for which there is supposedly something “proven”, and it is a complete brute force that is supposedly “exponential”. It is clear that branches with boundaries are exponential, but I have a question, gentlemen of mathematics: who dares to reject the hypothesis that there may exist a polynomial algorithm that will cut off obviously unpromising options even better than branches with boundaries? For example, it is so good to cut off that the number of candidate tours after clipping will be polynomial with respect to the number of nodes in the graph? There are such?
- The algorithm should be able to find both exact and “cheating-exact” solutions, since literally all existing TSP-problems consider the length of the edge, rounded to the whole — we will have to demonstrate that we can solve them in this mode too. The speed and quality of the algorithm should not be any noticeable depend on the accuracy of the calculations.
- The algorithm should work on a regular person and at the same time allow to calculate very large graphs, with millions of nodes. At present, the developed software allows counting graphs of up to about 100 million nodes (a little more), the largest of the test graphs actually solved by it has 123456789 nodes.
- Since TSP-tasks are usually multi-day, it should be possible to postpone the calculation at any time in order to resume it from the moment it is postponed at any time.
- Despite the fact that the vast majority of existing TSP-graphs are given as points on a plane or on a ball, we basically do not want to use their geometric features. This contradicts the formulation of the problem and, in fact, is the same scam as rounding. Of course, for real practical problems, it is possible and necessary to use all the possibilities, but we are not interested in developing a specific application, but in solving the problem in general. Therefore, we will not use, for example, such an obvious (and very efficient) method of splitting the original graph into subtasks by grouping the nodes according to the proximity of their coordinates. In a word, the algorithm should be indifferent whether the length is considered according to the coordinates of the nodes, whether it is given in tabular form, whether the so-called “triangle inequality” is fulfilled or not. So we’ll solve the traveling salesman problem by choice, while Keld Helsgaun, the author of the currently best method that found the lion’s share of existing best-known solutions, admits that 5 out of 6 heuristics of his algorithm are just geometric .
Of the whole variety of algorithms, we will consider only those that are based on the modification of the current round, i.e. Our approach is very similar to the classic Lin-Kernighan-Johnson method, like its LKH variant. However, there is a major difference: we use it to find not only an approximate, but also an exact solution. All the tools for this are already available, it remains only to throw away the "mutations" and all the other "ideas from tab search and evolutionary computing", replacing them (at least) with cascade recursion. After all, any accelerating heuristics at this stage only translates the problem from the exact category into approximate ones! We need it?
')
For a detailed check of all the concepts of our approach, we will conduct a large-scale experiment: we will re-solve all known problems, solved and not solved at the moment, including tasks from DIMACS TSP Challenge, and much more difficult to process graphs with hierarchical clustering of our own production, and uniformly random and all the rest. The result was a set of 395 traveling salesman tasks for graphs from 3 to 123456789 nodes.
Speed algorithm
The algorithm of the lowest possible modification of the tour by replacing two edges (2-opt) is elementary (two edges are removed from the tour, then the resulting chains are again connected to the tour with opposite ends), but very effective - this is the main “workhorse” with a speed modification of the tour - namely it falls the bulk of the fall of the beta border: up to 90% or more. Other algorithms of atomic modification (for example, the “double bridge”, which changes the edges according to the 4-opt scheme), are too expensive and are practically not used as almost useless.
So, we have a graph for which we must find the best tour. We don’t yet know anything about the graph itself and the current tour: the tour is probably optimal (such “miracles” are sometimes found - for example, in graph pr2392, nodes are carefully defined in such a sequence that, connecting the ribs to the second with the second, third, ... the last with the first we just get the best tour). Probably, the error is hundredths of a percent (if, for example, we try to improve the best-known solution for the graph w1904711), perhaps - many thousands of percent (say, the error for the same w1904711 at the start is more than 50,000%) - nothing about the algorithm is known. Therefore, he “assumes the worst,” and the main task of the speed algorithm is to “drop” the beta border as quickly as possible and as low as possible. In this case, it is highly desirable to consider not all the edges of the graph (which are still in the same w1904711 several trillion), but only a very small part of them, but exactly the one that allows us to reduce the beta border. Recall that we also have no information about the edges - they can even be given in tabular form. So are there any criteria for choosing the "right" edges? There are such criteria!
At the start, when loading the source data, we count the length of the current round and, dividing it by the number of nodes of the graph, we obtain the average edge length. Thus, each considered edge of the tour may be less, more, much more than this current average length. It is this information that controls the search: the longer the edge is, the more carefully it is considered: as the edge length increases by every 5% (actually, we have a little more - by 1/16) the depth of consideration (that is, the number of edges of the tour, starting with the current one, which verifies the possibility of atomic changes tour) doubles. However, short edges (in our case, these are edges of medium length and less) are considered only to the minimum depth, which is determined by the current iteration (the stage of finding a solution by any algorithm for all edges of a tour), and in general can be zero. In fact, this is the division of the original graph into subtasks, but the division is dynamic, in fact the elements of the group belong to one section of the current tour.
What does this give? A lot of things! With this approach, short edges at the lower iterations are almost not considered, i.e. the algorithm is not distracted by the “triviality”, and only those options that can give a serious decrease in the beta border look. With each solution found, the average length of the edge decreases, therefore, some edges that were previously considered “short” go into the category of “long” and are drawn into the search. On the contrary, the transition to the next iteration does not depend on the length of the tour, and is determined by the ratio of the number of solutions found during the iteration to the number of nodes of the graph. The meaning is obvious: there is no need to “call for help from the elders” while things are going well. Moreover, if the ratio is very high (tens of percent), it means that the tour managed to be well shattered, and it makes sense to return control to younger (faster) iterations, since the probability of their successful work is very high.
Generally speaking, the actually existing high-speed algorithm works about 10-100 times faster than the one just described, since there are many technical nuances when searching for a solution. We list the most important:
The lion's share of the performance provides the so-called "dobor". After the end of each iteration, if at the same time at least one solution was found, it is repeated, but only for new edges appearing at this iteration. There are usually very few such edges, but they have not yet been considered, and the probability of new solutions among them is quite high. As a result, the “dobor” is performed many times faster, and its efficiency often even exceeds the efficiency of the main iteration. Thus, each iteration reduces the beta border approximately twice as strong, and almost all of its decrease (90% or more) falls on the 2-3 lowest iterations, which significantly speeds up the passage of all other iterations. The program “dobor”, of course, is implemented within the framework of one iteration, which ends not after considering all the ribs of the tour, but after all of them, including the newly appeared ones, receive the status “examined”.
The concept of “minimum base depth” has been introduced (we have 64 edges) - this means that the high-speed algorithm does not have the right to finish the work, even if there is a complete failure to find solutions, until all edges are considered to this minimum depth. Such an approach practically guarantees that the high-speed algorithm will not pass the tour to the next processor with an error of hundreds and thousands of percent. For graphs with large errors in the starting tour, this minimum depth can grow “naturally” (if the iterations succeed in finding quite a lot of improvements in the tour) - I have seen the depth of 1024, and even 8192 (never seen again), but this is for graphs "millionaires." In any case, even such a depth is negligible compared to the number of nodes in the graph, so the operation time of the speed algorithm grows almost linearly in the number of nodes, which confirms the experiment.
Introduced the concept of "absolute edge". If for any edge the depth of calculation is half the nodes of the graph or more, the edge is calculated completely, to the full depth, and is marked as “absolute”, which will not be considered on any of their subsequent iterations of the speed search. For some types of graphs, this technique makes it possible to reduce the search time for a solution by several times.
At an ultra-small depth calculation of the current edge (up to 16), we only look at “turning the chain”, then some speed versions from the 3-opt series are connected, and at a depth of 64 (the minimum required depth) more “heavy” atomic algorithms. This reduces the running time of the speed algorithm by about half.
When processing “superlong” edges (with a length that is 8 or more times longer than the average), the decision to change the tour is made only with a decrease in the length of this particular edge, and not less than 1%. This not only shortens the search time at this iteration, minimizing “mouse fuss” on long edges, but also often noticeably drops the beta border, thus accelerating all other iterations.
There are many other nuances of implementation: limiting the difference in depth of calculating long and short edges, incrementing the length of the edge when choosing the depth to avoid unpleasant interference caused by rounding to the whole (sometimes it accelerates the calculation tenfold!), Technology for changing the basic depth of calculation between iterations, etc.
The experiment showed that the high-speed algorithm (which, as a rule, considers not all edges, sometimes much less than 1%) gives quite satisfactory results, suitable even for practical use. Beta-border with any size (usually it is 3-5 thousand percent of error) drops to 10-20%, rarely higher, often lower. The efficiency of the algorithm for super-large graphs has nothing to compare with: no program known to us can even begin calculating with hundreds of thousands of nodes (at least on a regular PC). In other words, we do not consider it necessary to further improve the speed algorithm. In the end, it is possible to use any heuristic algorithm you like, and its result can be “fed” to ours as input data. What we did when calculating the solution without rounding, substituting the “optimal” tour from TSPLIB as the initial one. Even in this case, the bulk of the solutions found also fall on the high-speed algorithm.
Well, enough, perhaps. It seems that there will also be 3-4 notes here, but how can I write them when I have so much spoiled karma that I can post no more than one note per week in this unfortunate “Recovery Mode”? O-ho-ho ...
Source: https://habr.com/ru/post/451300/
All Articles