2
$\begingroup$

So I just asked this question and accepted an answer, but I realized that I still don't understand this, and I can't access my previous question. We have the travelling salesman problem

Label the cities with the numbers $0, ...,n$ and define:

$x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise} \end{cases} $

For $i = 0, ...,n$, let $u_i$ be an artificial variable, and finally take $c_{ij}$ to be the distance from city $i$ to city $j$. Then TSP can be written as the following integer linear programming problem:

$\begin{align} \min &\sum_{i=0}^n \sum_{j\ne i,j=0}^nc_{ij}x_{ij} && \\ & 0 \le x_{ij} \le 1 && i,j=0, \cdots, n \\ & u_{i} \in \mathbf{Z} && i=0, \cdots, n \\ & \sum_{i=0,i\ne j}^n x_{ij} = 1 && j=0, \cdots, n \\ & \sum_{j=0,j\ne i}^n x_{ij} = 1 && i=0, \cdots, n \\ &u_i-u_j +nx_{ij} \le n-1 && 1 \le i \ne j \le n \end{align}$

The last constraint, $u_i-u_j +nx_{ij} \le n-1$ makes sure that there are no subtours. However, I don't see what this is. Wikipedia says the following:

To prove that every feasible solution contains only one closed sequence of cities, it suffices to show that every subtour in a feasible solution passes through city 0 (noting that the equalities ensure there can only be one such tour). For if we sum all the inequalities corresponding to $x_{ij}=1$ for any subtour of $k$ steps not passing through city 0, we obtain: $nk \leq (n-1)k$.

I don't understand this at all. How is the $nk \leq (n-1)k$ obtained? And how does this prevent there being any subtours at all? I have no clue.

As for the dummy variables, what purpose do they serve? Wikipedia says:

It now must be shown that for every single tour covering all cities, there are values for the dummy variables $u_i$ that satisfy the constraints.

But it doesn't at all explain why these dummy variables are necessary and what they add to the inequality. I'm stumped.

This question has been asked before here (but the answer doesn't help me at all) and here (by me, I thought it helped but it didn't), but none of the answers help and my question is slightly different, mostly focusing on how they obtained the expression $nk \leq (n-1)k$ and why this prevents subtours from forming

$\endgroup$

1 Answer 1

1
$\begingroup$

For your first question: suppose you have a solution to the linear program that has subtour $1 \to 2 \to 3 \to 1$. By assumption, the last set of inequalities holds, so if you add up the following, \begin{align} u_1-u_2 + n x_{12} &\le n-1\\ u_2-u_3 + n x_{23} &\le n-1\\ u_3-u_1 + n x_{31} &\le n-1, \end{align} you get $$3n \le 3(n-1).$$ This is a contradiction, so this subtour $1 \to 2 \to 3 \to 1$ does not exist.

In general for any subtour of length $k$ not including $0$, the same argument applies: adding up the inequalities corresponding to each edge of the subtour will give $kn \le k(n-1)$ because the $u_i$ terms will cancel.

$\endgroup$
1
  • $\begingroup$ If some subtour cannot exist, it does not mean that all subtours cannot exist. Although we can get how this extends to other subtours, this needs to be more rigourous. $\endgroup$
    – Element118
    Dec 11, 2015 at 22:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.