Integer Programming Traveling Salesman - Checking if Tour is Complete

Question

I'm reading a Wikipedia article on the Traveling Salesman problem as an Integer Programming formulation (http://en.wikipedia.org/wiki/Travelling_salesman_problem). The authors have all their constraints and I don't understand the final one. The following statement is in there.

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: n * k <= (n-1) * k

I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalites?

A little further the author states the following.

Without loss of generality, define the tour as originating (and ending) at city 0. Choose u[i]=t if city i is visited in step t (i, t = 1, 2, ..., n). Then u[i]-u[j] <= n-1, since u_i can be no greater than n and u_j can be no less than 1; hence the constraints are satisfied whenever x_{ij}=0. For x_{ij}=1, we have:

u[i] - u[j] + nx[ij] = (t) - (t+1) + n = n-1,

satisfying the constraint.

I guess I don't understand how this detects that we pass through all the nodes.

---

Okay, looking at this some more, I think I've discovered a bit more. This equation is the MTZ formulation (Miller-Tucker-Zemlin) and it's geared at finding subtours.

Having digested some snippets from papers like Gabor Pataki's Teaching Integer Programming Formulations using the Traveling Salesman Problem, there's a statement in there that if a subtour did not contain node 1, then along this subtour the u[i] value would have to increase to infinity. I'm not 100% sure, but what I think this means is that if you had nodes 3 and 4 linked together (edge from 3 to 4 and another from 4 to 3), you would have the following constraints...

$u_3 - u_4 + 1 \le (n-1)*(1-x_{34}) \le 0$

$u_4 - u_3 + 1 \le (n-1)*(1-x_{43}) \le 0$

The contradiction here is that $u_4$ is one step greater than $u_3$ which is one step greater than $u_4$.

Answer 1

First, an overview is as follows:

The last constraints enforce that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities.
To prove this, it is shown below (1) that every feasible solution contains only one closed sequence of cities, and (2) that for every single tour covering all cities, there are values for the dummy variables $u_i$ that satisfy the constraints.

Interpreting the last constraints as a theorem: $$u_i - u_j + n x_{ij} \le n - 1 \quad 1 \le i \neq j \le n \Leftrightarrow \text{there is only a single tour covering all cities.}$$ then part (1) is the necessary condition ("$\Rightarrow$"): every feasible solution in ILP implies a unique tour; and part (2) is the sufficient condition ("$\Leftarrow$"): every single tour corresponds to (at least) one feasible solution.

---

For your questions:

I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalities?

We aim to prove the part (1): every feasible solution contains only one closed sequence of cities. To this end, we should exclude the case that two or more disjointed subtours that only collectively cover all cities: For instance, subtours $0 \to 1 \to 2 \to 0 \bigcup 3 \to 4 \to 3 \bigcup 5 \to 6 \to 5$ covering all cities $0, \cdots, 6$ is not a legal tour, but it does satisfy the first and the second set of equalities.

Consider any subtour which does not pass through the city $0$ and sum the inequalities of $u_i - u_j + n x_{ij} \le n - 1 \quad 1 \le i \neq j \le n$ for the subtour (taking $3 \to 4 \to 3$ as an example):

Summing up $$(u_3 - u_4 + n \cdot 1 [x_{34} = 1] \le n-1) \text{ and } (u_4 - u_3 + n \cdot 1 [x_{43} = 1] \le n-1),$$ we have $$2n \le 2 (n-1).$$

Generally, for a subtour (which does not pass through the city $0$) with length $k$, we will get $nk \le (n-1) k$. Contradiction.

Therefore, every subtour must pass through the city $0$. Further, the first and the second equalities enforce that all subtours must be disjoint. As a consequence, there can only be a single tour covering all cities.

I guess I don't understand how this detects that we pass through all the nodes.

As I mentioned in the "overview", part (2) is the sufficient condition: We are given a single tour covering all cities, we aim to show that this tour corresponds to some feasible solution in this ILP. Because such a given tour trivially satisfies other constraints which do not involve these $u_i$ variables, it suffices to show that there are values for $u_i$ that satisfy the last constraints. This is proved by construction: Choose $u_{i}=t$ if city $i$ is visited in step $t$.