0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ We expect you to do a significant amount of research before asking here. If you don't understand a Wikipedia article, read original sources that explain this in more detail. So, what research and study have you done? What resources have you read? (Have you read the resources linked to on the Wikipedia page? Have you done other searching?) This topic is very well documented -- you should be able to find plenty of explanations of it. Wikipedia is a summary, not a primary source; it's a starting point for your research, not the end. $\endgroup$ – D.W. Feb 6 '15 at 22:56
  • $\begingroup$ @D.W. I'm asking for help here because my skills are obviously not as mature as others on this site. You're right that TSP is richly documented on the Internet. I have searched those however a lot of articles are not written for those that would require a more gentle introduction or they explore some facet of TSP that is beyond what I'm interested in or they discuss dynamic programming solutions, etc. If you don't like my question, please leave it for someone who is a little more understanding. Hopefully someone will teach me a thing that will allow me to become more independent in the future. $\endgroup$ – mj_ Feb 6 '15 at 23:16
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. Also, please integrate your edits so the question is always "one" post; a history is kept anyway. Furthermore, please be nice; snark does not help anyone. Exposing what you (don't) know in the question is crucial for getting (good) answers. $\endgroup$ – Raphael Feb 8 '15 at 13:56
  • $\begingroup$ @Raphael thank you for the welcome and the LaTeX link. I've updated my equations to conform. $\endgroup$ – mj_ Feb 8 '15 at 17:59
2
$\begingroup$

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

$\endgroup$

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.