Clarify the steps: what happened in this mathematical modelling of TSP?
$begingroup$
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.
graph-theory notation
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
$endgroup$
add a comment |
$begingroup$
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.
graph-theory notation
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
$endgroup$
add a comment |
$begingroup$
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.
graph-theory notation
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
$endgroup$
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.
graph-theory notation
graph-theory notation
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
asked Dec 9 '18 at 9:53
Ryan CameronRyan Cameron
697
697
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
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}, ineq 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 $3gt 2$.
answered Dec 9 '18 at 10:21
ip6ip6
54839
$endgroup$
$begingroup$
What is $E$ equal to, would it be correct to say, that it is equal to: $$E={v_{12}, v_{23}, v_{31}}$$ and so on?
$endgroup$
– Ryan Cameron
Dec 9 '18 at 10:43
$begingroup$
Yes that’s correct. And x_{ij} =1 if the edge is in the tour and =0 if not in the tour
$endgroup$
– ip6
Dec 9 '18 at 11:37
$begingroup$
If my answer resolved your question, please would you mind “accepting” it. If not, please leave another comment and i will explain further
$endgroup$
– ip6
Dec 10 '18 at 9:28
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: "69"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
noCode: 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%2fmath.stackexchange.com%2fquestions%2f3032212%2fclarify-the-steps-what-happened-in-this-mathematical-modelling-of-tsp%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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}, ineq 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 $3gt 2$.
answered Dec 9 '18 at 10:21
ip6ip6
54839
$endgroup$
$begingroup$
What is $E$ equal to, would it be correct to say, that it is equal to: $$E={v_{12}, v_{23}, v_{31}}$$ and so on?
$endgroup$
– Ryan Cameron
Dec 9 '18 at 10:43
$begingroup$
Yes that’s correct. And x_{ij} =1 if the edge is in the tour and =0 if not in the tour
$endgroup$
– ip6
Dec 9 '18 at 11:37
$begingroup$
If my answer resolved your question, please would you mind “accepting” it. If not, please leave another comment and i will explain further
$endgroup$
– ip6
Dec 10 '18 at 9:28
add a comment |
$begingroup$
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}, ineq 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 $3gt 2$.
answered Dec 9 '18 at 10:21
ip6ip6
54839
$endgroup$
$begingroup$
What is $E$ equal to, would it be correct to say, that it is equal to: $$E={v_{12}, v_{23}, v_{31}}$$ and so on?
$endgroup$
– Ryan Cameron
Dec 9 '18 at 10:43
$begingroup$
Yes that’s correct. And x_{ij} =1 if the edge is in the tour and =0 if not in the tour
$endgroup$
– ip6
Dec 9 '18 at 11:37
$begingroup$
If my answer resolved your question, please would you mind “accepting” it. If not, please leave another comment and i will explain further
$endgroup$
– ip6
Dec 10 '18 at 9:28
add a comment |
$begingroup$
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}, ineq 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 $3gt 2$.
answered Dec 9 '18 at 10:21
ip6ip6
54839
$endgroup$
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}, ineq 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 $3gt 2$.
answered Dec 9 '18 at 10:21
ip6ip6
54839
answered Dec 9 '18 at 10:21
ip6ip6
54839
answered Dec 9 '18 at 10:21
ip6ip6
54839
answered Dec 9 '18 at 10:21
ip6ip6
54839
54839
$begingroup$
What is $E$ equal to, would it be correct to say, that it is equal to: $$E={v_{12}, v_{23}, v_{31}}$$ and so on?
$endgroup$
– Ryan Cameron
Dec 9 '18 at 10:43
$begingroup$
Yes that’s correct. And x_{ij} =1 if the edge is in the tour and =0 if not in the tour
$endgroup$
– ip6
Dec 9 '18 at 11:37
$begingroup$
If my answer resolved your question, please would you mind “accepting” it. If not, please leave another comment and i will explain further
$endgroup$
– ip6
Dec 10 '18 at 9:28
add a comment |
$begingroup$
What is $E$ equal to, would it be correct to say, that it is equal to: $$E={v_{12}, v_{23}, v_{31}}$$ and so on?
$endgroup$
– Ryan Cameron
Dec 9 '18 at 10:43
$begingroup$
Yes that’s correct. And x_{ij} =1 if the edge is in the tour and =0 if not in the tour
$endgroup$
– ip6
Dec 9 '18 at 11:37
$begingroup$
If my answer resolved your question, please would you mind “accepting” it. If not, please leave another comment and i will explain further
$endgroup$
– ip6
Dec 10 '18 at 9:28
$begingroup$
What is $E$ equal to, would it be correct to say, that it is equal to: $$E={v_{12}, v_{23}, v_{31}}$$ and so on?
$endgroup$
– Ryan Cameron
Dec 9 '18 at 10:43
$begingroup$
What is $E$ equal to, would it be correct to say, that it is equal to: $$E={v_{12}, v_{23}, v_{31}}$$ and so on?
$endgroup$
– Ryan Cameron
Dec 9 '18 at 10:43
$begingroup$
Yes that’s correct. And x_{ij} =1 if the edge is in the tour and =0 if not in the tour
$endgroup$
– ip6
Dec 9 '18 at 11:37
$begingroup$
Yes that’s correct. And x_{ij} =1 if the edge is in the tour and =0 if not in the tour
$endgroup$
– ip6
Dec 9 '18 at 11:37
$begingroup$
If my answer resolved your question, please would you mind “accepting” it. If not, please leave another comment and i will explain further
$endgroup$
– ip6
Dec 10 '18 at 9:28
$begingroup$
If my answer resolved your question, please would you mind “accepting” it. If not, please leave another comment and i will explain further
$endgroup$
– ip6
Dec 10 '18 at 9:28
add a comment |
Thanks for contributing an answer to Mathematics 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.
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%2fmath.stackexchange.com%2fquestions%2f3032212%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
