$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong to the tour, have smaller weightsum and yield a different tour when exchanged with the selected tour-edges; cf e.g General k-opt submoves for the Lin–Kernighan TSP heuristic.

My impression is that no polynomial size $\mathrm{LP}$-formulations for finding $\mathrm{k}$-$\operatorname{opt}$ moves are available and that in implementations $\mathrm{k}$ is limited to very small fixed values, e.g. $5$.

Question:is my impression right that no polynomial size $\mathrm{LP}$-formulations for $\mathrm{k}$-$\operatorname{opt}$ moves are known, not even for fixed $\mathrm{k}$, resp. which such formulations are known and what can be said about their integrality gap?

It appears to me that candidate edge-sets whose exchange results in a cycle cover of lower weight, that *may* be a tour, can be found by polynomial size $\mathrm{LP}$'s and that there are polynomial size $\mathrm{ILP}$-formulations that reliably identify edge-sets whose exchange *yields* a shorter tour but whose $\mathrm{LP}$ relaxation may have an integrality gap.