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.
Timp de mulți ani, Lin–Kernighan–Johnson a identificat soluții optime pentru toate PCV-urile atunci când era cunoscută o soluție optimă și a identificat cele mai bune soluții cunoscute pentru toate celelalte PCV-uri pe care a fost încercată.