There are $n$ cities and the distance between a city $i$ and a city $j$ is given by $c_{ij}$ for $i,j = 1,2,...,n$ where we have $c_{ii} = \infty$ for all $i$. A salesman has to make a trip through all cities in a way that the total travelling distance is minimal. We make this a combinatorial optimisation problem by introducing $(0,1)$ variables $x_{ij}$ with the following meaning: $x_{ij} = 0$ means the direct route from city $i$ to city $j$ is not chosen, $x_{ij} = 1$ means it is chosen.
So I thought this problem could be written down as follows:
$$ \min \left\{ \displaystyle \sum_{i,j =1}^n c_{ij}x_{ij} \begin{array}{lr} \big\rvert \sum_{i=1}^n x_{ij} = 1,1 \leq j \leq n \\ \big\rvert \sum_{i=1}^n x_{ji} = 1, 1 \leq j \leq n \\ \big\rvert x_{ij} \in \{0\} \text{for every} (i,j) \end{array} \right\}$$
Where $\sum_{i=1}^n x_{ij} = 1,1 \leq j \leq n$ means that for each city $j$ there is one city from which $j$ can be visited, and $\sum_{i=1}^n x_{ji} = 1, 1 \leq j \leq n$ means that we go to just one city from each city $j$.
However, this is apparently incorrect for some reason I don't understand. I was also told that my method is correct if you add the following:
$u_i - u_j + nx_{ij} \leq n-1$ for every $i,j \geq 2$ and $u_i \geq 0$ and integer for $i =1,2,...,n$.
(let the route start in city 1 and interpret $u_i = k$, where city $i$ is the k-th city to be visited from city 1)
However, this correction doesn't help me at all because I don't understand it. Can someone please understand what's wrong with my function and why the above addition rectifies it?
edit: I now know why my function is wrong because of the given answer, but I still don't know how it's rectified by the added constraint.
