# travelling salesman understanding constraints

I am trying to program TSP problem in R. From wikipedia page section "Integer linear programming formulation", I was able to understand all the constraints except the last one.

Need help to understand the last constraint...what are the variable U/artificial varaibles? are they slack variables for earlier constraints?

• For more info about that formulation, and the meaning of that constraint and variables, you may want to look for the MTZ (Miller-Tucker-Zemlin) formulation of the TSP. As already pointed out in @Boris Novikov's answer, those variables are used to avoid sub-tours in the solution. docs.mosek.com/6.0/capi/node015.html – Libra Oct 5 '13 at 8:56

This constraint is introduced to avoid disconnected routes of the salesman. Indeed, if a route consists of more than one cycle, then summing the last constraints along the cycle with the length $k<n$, we obtain $nk\le n(k-1),$ which is impossible.
Addendum: Let we begin to solve a TSP by a method of the integer programming. On the first step we choose anywise the unknowns $x_{ij}=0,1$ and $u_i$. Thanking to the last constraints we necessarily get a connected route. The same thing happens on the second step etc. So we will only deal with connected routes.