# Clarify the steps: what happened in this mathematical modelling of TSP?

I don't get this part: (look at the source)

$$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1$$

I get that $$x_{ij}$$ is equal to 3, but why the "> 2" ?

And what is the deal with subtracting 1 from a set? How do you even do that?

How come $$|\{1,2,3\}|-1 = 3 > 2$$ ?!?

Okay so: $$|\{1,2,3\}|-1 = 2$$

So how is he allowed to write: $$|\{1,2,3\}|-1 = 3 > 2$$

?

That is basically the same as writing: (which is incorrect right?) $$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 math level.

• $3 \gt 2$ is what they imply I think. The remaining part subtracts 1 from the cardinality of the set and not the set itself. The cardinality of the set is the number of elements in it. Here, the set has 3 elements so you get 2 if you subtract 1 from the cardinality – kauray Dec 9 '18 at 10:01
• This is the very common practice of chaining (in)equalities. Think of it as $3 > 2$ and $2 = 3 - 1$ being chained together as $3 > 2 = 3 - 1$. – Alex Vong Dec 9 '18 at 18:43

The point of these constraints is eliminating subtours, which the source explains quite clearly. So for every subset $$S$$ of the nodes, such as $$\{1,2,3\}$$, they add a constraint which says $$\Sigma_{i,j \in S, i \neq j} x_{ij} \leq |S| - 1$$. So when this constraint is satisfied, there is no way to form a cycle on the vertices in $$S$$.

Now, if this constraint was not satisfied (i.e., the number of edges was at least $$|S|$$), then a cycle could be formed like they show in their figures. For example, on $$\{1,2,3\}$$, you can form a triangle (which is a cycle) if you use 3 edges.

Particularly regarding your confusion, note that they have written $$|S|-1$$ (and not $$S-1$$). Here, $$|S|$$ refers to the size of the set $$S$$ (also known as the cardinality of $$S$$), so $$|\{1,2,3\}| = 3$$. Further, notice that they don't write $$2 = 3 > 2$$, but instead $$3 > 2 = 3 - 1$$. If it's clearer, you can also assume the constraint just says $$3 > |\{1,2,3\}| - 1$$.

• Question, What does "S≠∅" Mean? That the subset should not be none/empty? – Ryan Cameron Dec 9 '18 at 10:51
• @Ryan $\emptyset$ stands for the set with no elements, i.e., the empty set. So you are exactly right. – Juho Dec 9 '18 at 10:56

You seem to have misunderstood pretty much every part of the statement

$$\sum_{i,j\in\{1,2,3\},i\neq j} x_{ij}=3>2=|\{1,2,3\}|-1\,.$$

I get that $$x_{ij}$$ is equal to 3,

No, the sum of all values $$x_{ij}$$ where $$i$$ and $$j$$ are distinct values from $$\{1,2,3\}$$ is equal to $$3$$.

but why the "> 2" ?

Because three is bigger than two.

And what is the deal with subtracting 1 from a set? How do you even do that?

No, it's subtracting one from the cardinality of the set. Notice the $$|\dots|$$.

How come $$|\{1,2,3\}|-1 = 3 > 2$$ ?!?

It isn't. When we write something like $$A=B>C=D$$, it means that $$A=B$$, $$B>C$$ and $$C=D$$. You can't just re-order the terms and expect the statement to remain true, just as you can't reorder $$3>2$$ as $$2<3$$ and expect it to remain true.

So, the statement as a whole means:

• The sum of the values $$x_{ij}$$ is equal to $$3$$.
• Also, $$3>2$$.
• Also, $$2=|\{1,2,3\}|-1$$.

So how is he allowed to write: $$|\{1,2,3\}|-1 = 3 > 2\,?$$

He isn't and he doesn't.

• Sorry, I am confused. Regarding the sum of all values xij where i and j are distinct values from {1,2,3} is equal to 3. So I get distinct values 1 and 3 from the set where sum is not 3. So I am not understanding, can you help please? What do you mean sum of all values xij where i and j are distinct? – Koray Tugay Dec 9 '18 at 16:01
• @KorayTugay In this context, $x_{i,j}$ exists only when $i<j$, so the sum above is $x_{1,2}+x_{1,3}+x_{2,3}$ and the result of this is 3 (since it's $1+1+1$, in the considered example). You don't sum the indices, you sum the values of all the numbers $x_{i,j}$. – chi Dec 9 '18 at 16:05
• @KorayTugay I think the underlying problem here is that you don't understand mathematical notation. I suggest you talk to your school maths teacher about that, because you need more interactive help than we can really give on this site. – David Richerby Dec 9 '18 at 16:06
• @chi I see thanks I understand. You count the possible combinations. Thanks. – Koray Tugay Dec 9 '18 at 17:46
• @RyanCameron My suggestion to understanding $\sum$ notation is to expand it out. By definition, we can write $$\sum_{i, j \in \{1, 2, 3\}, i \neq j} x_{ij} = x_{12} + x_{13} + x_{21} + x_{23} + x_{31} + x_{32}$$ I remember my number theory professor used to write $$\sum_{\substack{1 \le i, j \le 3 \\ i \neq j}} x_{ij}$$ which I think is less formal and more readable. – Alex Vong Dec 9 '18 at 19:04