The traveling salesman problem (TSP) is one of the most widely studied problems in combinatorial optimization. Given a collection of cities and the cost of travel between each pair of them, the traveling salesman problem is to find the cheapest way of visiting all of the cities and returning to the starting point.

TSP may also be stated as the problem of finding a Hamiltonian cycle (tour) of minimum weight in an edge-weighted graph. 

The Lin-Kernighan algorithm belongs to the class of so-called local search algorithms. 

A local search algorithm starts at some location in the search space and subsequently moves from the present location to a neighboring location.

The algorithm is specified in exchanges that can convert one candidate solution into another. 

Given a feasible TSP tour, the algorithm repeatedly performs exchanges that reduce the length of the current tour, until a tour is reached for which no exchange yields an improvement. This process may be repeated many times from initial tours generated in some randomized way. 

The Lin-Kernighan algorithm (LK) performs so-called k-opt moves on tours. A k-opt move changes a tour by replacing k edges from the tour by k edges in such a way that a shorter tour is achieved.