1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Libra Oct 5 '13 at 8:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I knew purpose of that constraint but what i dont know is what are the variable U/artificial variables that are mentioned on Wikipedia? are they slack variables for earlier constraints? $\endgroup$ – user2543622 Oct 4 '13 at 20:54
  • $\begingroup$ No, they are not slack variables, i.e. they don't transform some inequalities into equalities. They take part only in the last constraints. $\endgroup$ – Boris Novikov Oct 4 '13 at 21:16
  • $\begingroup$ i am still not clear :( They are not part of the Minimization objective. They dont appear in other constraints then how do they affect the solution? what is the meaning of 'artificial variables'? $\endgroup$ – user2543622 Oct 4 '13 at 22:41
  • $\begingroup$ by 'they' i mean U variable $\endgroup$ – user2543622 Oct 4 '13 at 23:09
  • $\begingroup$ @Cameron Buie: Thank you very much. $\endgroup$ – Boris Novikov Oct 5 '13 at 6:53

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.