0
$\begingroup$

Source: http://examples.gurobi.com/traveling-salesman-problem

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.

$\endgroup$
2
  • $\begingroup$ $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 $\endgroup$
    – kauray
    Dec 9, 2018 at 10:01
  • $\begingroup$ 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$. $\endgroup$
    – Alex Vong
    Dec 9, 2018 at 18:43

2 Answers 2

2
$\begingroup$

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$.

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

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Dec 9, 2018 at 16:01
  • 1
    $\begingroup$ @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}$. $\endgroup$
    – chi
    Dec 9, 2018 at 16:05
  • 2
    $\begingroup$ @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. $\endgroup$ Dec 9, 2018 at 16:06
  • $\begingroup$ @chi I see thanks I understand. You count the possible combinations. Thanks. $\endgroup$ Dec 9, 2018 at 17:46
  • $\begingroup$ @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. $\endgroup$
    – Alex Vong
    Dec 9, 2018 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.