patternMinor
$k$-Opt TSP Local Search is NOT exact when $k = \lceil |V|/2 \rceil$
Viewed 0 times
exactlocaltspsearchoptrceilwhennotlceil
Problem
I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani.
I am having a hard time with a question about local search involving the traveling salesman problem (TSP).
We'll say a local search algorithm is exact if it always returns a globally optimal solution.
Consider a local search algorithm for TSP that uses neighborhoods defined by $k$-change: two tours $T_0$ and $T_1$ are neighbors if one can delete $j \leqslant k$ edges from $T_0$ and add back another $j$ edges to obtain $T_1$.
This is known as the $k$-Opt algorithm.
It's easy to see and the book itself discusses how for low values of $k$ (relative to the number $n$ of vertices), $k$-Opt may get stuck on locally optimal solutions that are not globally optimal.
In other words, $k$-Opt is not exact for these values of $k$.
The exercise I'm interested in claims that
$k$-Opt with $k = \lceil n/2 \rceil$ is not exact.
I've tried my hand and searched around but couldn't make it.
I found the paper "Some Examples of Difficult Traveling Salesman Problems", available here (and Papadimitriou is one of the authors by the way).
It contains a family of examples for which $k$-Opt with $k < (3n/8)$ is not exact, and uses a particular kind of subgraph (which it calls the diamond) to impose a structure on feasible tours.
I've tried to replicate and extend something like this with little success.
I am having a hard time with a question about local search involving the traveling salesman problem (TSP).
We'll say a local search algorithm is exact if it always returns a globally optimal solution.
Consider a local search algorithm for TSP that uses neighborhoods defined by $k$-change: two tours $T_0$ and $T_1$ are neighbors if one can delete $j \leqslant k$ edges from $T_0$ and add back another $j$ edges to obtain $T_1$.
This is known as the $k$-Opt algorithm.
It's easy to see and the book itself discusses how for low values of $k$ (relative to the number $n$ of vertices), $k$-Opt may get stuck on locally optimal solutions that are not globally optimal.
In other words, $k$-Opt is not exact for these values of $k$.
The exercise I'm interested in claims that
$k$-Opt with $k = \lceil n/2 \rceil$ is not exact.
I've tried my hand and searched around but couldn't make it.
I found the paper "Some Examples of Difficult Traveling Salesman Problems", available here (and Papadimitriou is one of the authors by the way).
It contains a family of examples for which $k$-Opt with $k < (3n/8)$ is not exact, and uses a particular kind of subgraph (which it calls the diamond) to impose a structure on feasible tours.
I've tried to replicate and extend something like this with little success.
Solution
Answer to the first question:
Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.
Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.
Why colored tour is locally optimal?
Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.
After adding these edges, we can not keep edges $(B,D)$ and $(A,G)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$. Now, we must remove edges $(B,E)$ and $(A,F)$.
To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.
This proves that the tour formed by colored edges is locally optimal.
The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.
Please see the following figure for $n = 8$. All the red and black edges have weight $1$. The green edge $(C,H)$ has weight $2$. And, the blue edges have weight $0$. The edges that are not there have weight $\infty$; I have not drawn these edges for simplicity.
Now, note that the cycle $(A,B,C,D,E,F,G,H)$ is the optimal tour with weight $5$. Also, the tour formed by the colored edges (red, green, and blue) has weight $6$. Note that the tour formed by these colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.
Why colored tour is locally optimal?
Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $(C,H)$ must be replaced and the blue edges can not to be replaced. If we replace edge $(C,H)$, then we must add the edges $(C,B)$ and $(A,H)$; otherwise, the weight of the tour will become $\infty$.
After adding these edges, we can not keep edges $(B,D)$ and $(A,G)$ in the tour. Therefore, we must add edges $(D,E)$ and $(G,F)$; otherwise, the weight of the tour will become $\infty$. Now, we must remove edges $(B,E)$ and $(A,F)$.
To complete the tour, we need to add edge $(A,B)$; however, we can not add any more edges since we have already added $4 = n/2$ new edges. Therefore, a tour can only be formed by adding edges $(B,F)$ and $(E,A)$. It makes the weight of the tour $\infty$.
This proves that the tour formed by colored edges is locally optimal.
The technique can be easily generalized to the general value of $n$. For example, see the following figure for $n = 14$. Here, again, the tour formed by the colored edges is locally optimal to $\lceil n/2 \rceil$ change but it is not globally optimal.
Context
StackExchange Computer Science Q#149234, answer score: 3
Revisions (0)
No revisions yet.