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