Cfrtjryk

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

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

$$sum_{i,jin{1,2,3},ineq 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.

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

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

$$sum_{i,jin{1,2,3},ineq 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.