Editing Travelling salesman problem (section)

==== ''V''-opt heuristic ====
The variable-opt method is related to, and a generalization of, the ''k''-opt method. Whereas the ''k''-opt methods remove a fixed number (''k'') of edges from the original tour, the variable-opt methods do not fix the size of the edge set to remove. Instead, they grow the set as the search process continues. The best-known method in this family is the Lin–Kernighan method (mentioned above as a misnomer for 2-opt). [[Shen Lin]] and [[Brian Kernighan]] first published their method in 1972, and it was the most reliable heuristic for solving travelling salesman problems for nearly two decades. More advanced variable-opt methods were developed at Bell Labs in the late 1980s by David Johnson and his research team. These methods (sometimes called [[Lin–Kernighan–Johnson]]) build on the Lin–Kernighan method, adding ideas from [[tabu search]] and [[evolutionary computing]]. The basic Lin–Kernighan technique gives results that are guaranteed to be at least 3-opt. The Lin–Kernighan–Johnson methods compute a Lin–Kernighan tour, and then perturb the tour by what has been described as a mutation that removes at least four edges and reconnects the tour in a different way, then ''V''-opting the new tour. The mutation is often enough to move the tour from the [[local minimum]] identified by Lin–Kernighan. ''V''-opt methods are widely considered the most powerful heuristics for the problem, and are able to address special cases, such as the Hamilton Cycle Problem and other non-metric TSPs that other heuristics fail on. For many years, Lin–Kernighan–Johnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best-known solutions for all other TSPs on which the method had been tried.