Clarify the steps: what happened in this mathematical modelling of TSP?
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.
traveling-salesman notation
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
asked Dec 9 '18 at 9:51
Ryan Cameron
316
add a comment |
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.
traveling-salesman notation
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
asked Dec 9 '18 at 9:51
Ryan Cameron
316
$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
– Kaustabha Ray
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
add a comment |
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.
traveling-salesman notation
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
asked Dec 9 '18 at 9:51
Ryan Cameron
316
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.
traveling-salesman notation
traveling-salesman notation
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
asked Dec 9 '18 at 9:51
Ryan Cameron
316
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
asked Dec 9 '18 at 9:51
Ryan Cameron
316
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
edited Dec 9 '18 at 11:42
David Richerby
66k15100190
66k15100190
asked Dec 9 '18 at 9:51
Ryan Cameron
316
asked Dec 9 '18 at 9:51
Ryan Cameron
316
asked Dec 9 '18 at 9:51
Ryan Cameron
316
316
$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
– Kaustabha Ray
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
add a comment |
$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
– Kaustabha Ray
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
$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
– Kaustabha Ray
Dec 9 '18 at 10:01
$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
– Kaustabha Ray
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
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
add a comment |
2 Answers
2
active
oldest
votes
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$.
answered Dec 9 '18 at 10:23
Juho
15.2k54089
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
add a comment |
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.
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
Sorry, I am confused. Regardingthe 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 meansum of all values xij where i and j are distinct?
– Koray Tugay
Dec 9 '18 at 16:01
1
@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
2
@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
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f101270%2fclarify-the-steps-what-happened-in-this-mathematical-modelling-of-tsp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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$.
answered Dec 9 '18 at 10:23
Juho
15.2k54089
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
add a comment |
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$.
answered Dec 9 '18 at 10:23
Juho
15.2k54089
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
add a comment |
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$.
answered Dec 9 '18 at 10:23
Juho
15.2k54089
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$.
answered Dec 9 '18 at 10:23
Juho
15.2k54089
edited Dec 9 '18 at 10:35
answered Dec 9 '18 at 10:23
Juho
15.2k54089
answered Dec 9 '18 at 10:23
Juho
15.2k54089
answered Dec 9 '18 at 10:23
Juho
15.2k54089
15.2k54089
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
add a comment |
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
Question, What does "S≠∅" Mean? That the subset should not be none/empty?
– Ryan Cameron
Dec 9 '18 at 10:51
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
@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
add a comment |
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.
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
Sorry, I am confused. Regardingthe 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 meansum of all values xij where i and j are distinct?
– Koray Tugay
Dec 9 '18 at 16:01
1
@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
2
@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
add a comment |
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.
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
Sorry, I am confused. Regardingthe 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 meansum of all values xij where i and j are distinct?
– Koray Tugay
Dec 9 '18 at 16:01
1
@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
2
@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
add a comment |
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.
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
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.
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
answered Dec 9 '18 at 11:51
David Richerby
66k15100190
66k15100190
Sorry, I am confused. Regardingthe 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 meansum of all values xij where i and j are distinct?
– Koray Tugay
Dec 9 '18 at 16:01
1
@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
2
@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
add a comment |
Sorry, I am confused. Regardingthe 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 meansum of all values xij where i and j are distinct?
– Koray Tugay
Dec 9 '18 at 16:01
1
@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
2
@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
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
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
1
1
@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 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
2
2
@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
@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
@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
@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
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f101270%2fclarify-the-steps-what-happened-in-this-mathematical-modelling-of-tsp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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
– Kaustabha Ray
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