1
$\begingroup$

$\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.

$\endgroup$

1 Answer 1

0
$\begingroup$

For a simplified formulation of necessary constraints for $\mathrm{k}$ moves it is assumed that the vertices have been relabeled so that $0,\,\dots,\,n-1$ reflects the order in which they are encountered when the tour is traveled.

Then three necessary conditions that can be identified are

  • degree conservation constraints:
    for every vertex the number of adjacent in-edges must be equal to the number of adjacent out-edges
  • what comes in must go out constraints: for every vertex $i$ the sum of ingoing edges of its neighbors $i-1$ and $i+1$ must not be smaller than the number of $i$'s ingoing edges.
  • subtour elimination constraints:
    if $\mathrm{X}$ is graph induced by the union of tour-edges and in-edges, then no in-edges $f_{ij}$ must exist such that $\mathrm{X}\setminus\lbrace i,\,j\rbrace$ is disconnected because otherwise every exchange set that contains $f_{ij}$ would result in a disconnected cycle cover.

The corresponding linear program can then be formulated as

\begin{align*} \text{min} \quad \tau^\prime x\ +\ \sigma^\prime y & \\ \text{s.t.} \quad x_{i-1,i}+x_{i,i+1}&=\sum\limits_{2\le\left|j-i\right|}y_{ij} \\ \sum\limits_j y_{ij} &\le \sum\limits_j y_{i-1,j}+\sum\limits_j y_{i+1,j}\\ y_{ij} &\le\sum\limits_{i\lt u\lt j\lt v}y_{uv}\quad+\sum\limits_{u\lt i\lt v\lt j}y_{uv}\\ x_{i,i+1},x_{n-1,0}\,,\, y_{ij} &\in\lbrace 0,1\rbrace \end{align*}

where $\tau$ is the vector of tour-edge weights and $\sigma$ the vector of non-tour edge weights; additons and subtraction of indices corresponding to vertex labels are to be understood modulo $n$

The degree conservation constraints are analogous to the flow conservation constraints and would thus yield an integral solution if the subtour elimination constraints were not part of the above linear program.
Most likely the subtour elimation constraints will lead to non-integral solutions.

A further thought is as to whether utilizing MTZ constraints for subtour elimination would be worthwile to investigate.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy