Source: http://examples.gurobi.com/traveling-salesman-problem
I don't get this part: (look at the source)
I get that $x_{ij}$ is equal to 3, but why the "> 2" ?
And what is the deal with subtracting one from a set? How do you even do that?
How come $|\{1,2,3\}|-1 = 3 > 2$ ?!?
Isn't $$|\{1,2,3\}|-1=3>2$$ The same as writing: $$2=3>2$$ ?
I don't get this part at all, please elaborate on what happened in as simple language as possible. My level is high school final year.
It’s a slightly confusing way of writing it especially if you are used to reading everything left to right.
Expanded, what the author is saying is that the “no subtour” constraint is
$$\sum_S x_{i,j} \leq \left| S \right| -1$$
The number of edges involved in any proper subset S is at most the number of points (cities) minus one.
Take the left hand side of this constraint for the set $\{1,2,3\}$
$$\sum_{i,j \in \{1,2,3\}, i\neq j}x_{i,j} = 3$$
And the RHS is
$$\left|\{1,2,3\}\right|-1 =2$$
Where $\left|\{1,2,3\}\right|$ is the number of elements in the set, ie 3.
The constraint is violated since $3\gt 2$.