Editing Travelling salesman problem (section)

==== ''k''-opt heuristic, or Lin–Kernighan heuristics ====
The [[Lin–Kernighan heuristic]] is a special case of the ''V''-opt or variable-opt technique. It involves the following steps:

# Given a tour, delete ''k'' mutually disjoint edges. 
# Reassemble the remaining fragments into a tour, leaving no disjoint subtours (that is, do not connect a fragment's endpoints together). This in effect simplifies the TSP under consideration into a much simpler problem.
# Each fragment endpoint can be connected to {{math|2''k''&nbsp;−&nbsp;2}} other possibilities: of 2''k'' total fragment endpoints available, the two endpoints of the fragment under consideration are disallowed. Such a constrained 2''k''-city TSP can then be solved with brute-force methods to find the least-cost recombination of the original fragments.

The most popular of the ''k''-opt methods are 3-opt, as introduced by Shen Lin of [[Bell Labs]] in 1965. A special case of 3-opt is where the edges are not disjoint (two of the edges are adjacent to one another). In practice, it is often possible to achieve substantial improvement over 2-opt without the combinatorial cost of the general 3-opt by restricting the 3-changes to this special subset where two of the removed edges are adjacent. This so-called two-and-a-half-opt typically falls roughly midway between 2-opt and 3-opt, both in terms of the quality of tours achieved and the time required to achieve those tours.