Edit 2017-04-20
meanwhile I have a better understanding of $k$-optimality and, following a suggestion of Stefan Kohl, I report it here in the spirit of sharing knowledge, even if there isn't a 100% relation to the stated problem.
Efficiently finding optimal replacements for subsets of tour-edges:
the problem, that has to be solved here, is to report the optimal replacement for $k$ of a tour's edges
The key observation were:
that a subset of $k$ edges of a tour defines a linear forest, whose number of connected components can be anything from $1$ to $k$ and, that the number of connected components of the complement, i.e., of the "unselected" edges of same tour, equals that of the selected edges
for finding the optimal replacement for $k$ of a tour's edges, the set of unselected edges trivially doesn't influence the relative order of the candidate replacement sets; therefore it is possible, to formally retract each connected component of the unselected edges (lets call those components the "plumes" of a tour) to a "plume-edge".
The optimal set of replacement-edges is then the one, that constitutes to the optimal tour through subgraph that is induced by the adjacent vertices and, after setting the weight of the plume-edges to $0$ and adding a sufficiently high value to the other edges, so that it is guaranteed, that the plume-edges are contained in the optimal tour.
Reducing the problem of finding the optimal set of replacement edges to a fixed-size tsp, provides an entire arsenal of algorithms from brute force over branch-and-bound to LP based solvers.
Generating all optimization instances for optimally replacing $k$ of a tour's edges:
- the key observation was, that the plume-edges are pairwise not adjacent and thus are adjacent $2h$ vertices, $1\le h\le\lfloor\frac{k}{2}\rfloor$.
Every optimization instance for $k$ tour edges can therefore be represented by $h$ plume-edges plus $k-2h$ non-adjacent vertices.
The only algorithmic challenge is to avoid generating an optimization instance multiple times, which in turn means to generate each set of plume-edges only once.
That can however be guaranteed by creating those tuples in ascending order of the smaller of the adjacent vertices and then, proceeding backwards trough the list of generated first vertices,
iterate from the an plume-edge's first vertex to the end of the vertex list, skipping vertices, that are already the second vertex of a plume-edge.
Generalizing intersection or crossing of two edges to $k$ edges:
- the key observation was, that two geometrically intersecting or crossing edges (i.e. the maximum matching of a K_4 subgraph) can't simultaneously appear in an optimal tour.
That same "mutex" situation can be identified in the $k$-optimal sets of replacement edges: if a pair vertices $\lbrace u,v\rbrace$ can be found in two such optimal replacement sets, in which $\lbrace u,v\rbrace$ isn't adjacent to a plume-edge and, if $(u,v)$ is an edge in one set, but not in the other, then those two sets are also mutually exclusive and can be defined as "crossing".
Generalizing separators to $k$-separators
a $k$-separator is an edge, that can't be part of any $k$-optimal tour, i.e. when removing all mutually exclusive edges and the two adjacent vertices renders the graph disconnected.
That generalizes directly to $k$-optimality by removing all incompatible replacement sets and the vertices that define the candidate edge.
Generalizing geometric convex hulls to $k$-opt hulls
the striking property of planar geometric convex hulls is, that the order of points on the convex hull is preserved int the optimal tour.
The defining properties can be described as follows:
it can be constructed from the largest triangle via greedy expansion, that preserves the property, that all edges, except the hull edges, are separator edges.
That construction also generalizes directly to $k$-optimality, because any permutation of the hull-vertices would create a tour with $k$-separators and could thus not be $k$-optimal.
