Location problem — linear programming
$begingroup$
I have a location problem I need help with:
Suppose a boat company wants to operate services between 11 ports in a city. The number of return journeys between port i and port j is denoted by a x-variable (Xij), i and j = 1 to 11. Now I need to impose a constraint such that the number of return journeys between the same pair of ports does not exceed 3. That is, e.g. there can be at most 3 return journeys made between port 1 and port 2.
I know I can do it by Xij + Xji <= 3, but this would result in tons of constraints...
Can anyone come up with a compact form of this constraint? Thank you in advance!
linear-programming integer-programming
asked Dec 18 '18 at 11:47
HFCHHFCH
83
$endgroup$
add a comment |
$begingroup$
I have a location problem I need help with:
Suppose a boat company wants to operate services between 11 ports in a city. The number of return journeys between port i and port j is denoted by a x-variable (Xij), i and j = 1 to 11. Now I need to impose a constraint such that the number of return journeys between the same pair of ports does not exceed 3. That is, e.g. there can be at most 3 return journeys made between port 1 and port 2.
I know I can do it by Xij + Xji <= 3, but this would result in tons of constraints...
Can anyone come up with a compact form of this constraint? Thank you in advance!
linear-programming integer-programming
asked Dec 18 '18 at 11:47
HFCHHFCH
83
$endgroup$
$begingroup$
an alternative is Benders' decomposition, but I'd rather add those 55 constraints
$endgroup$
– LinAlg
Dec 18 '18 at 17:55
$begingroup$
Think I'd rather do the same as well and keep it simple, thanks!
$endgroup$
– HFCH
Dec 18 '18 at 18:08
$begingroup$
It is just one line: $large{x_{ij}+x_{ji}leq 3 forall i,jin {1,2, ldots , 11}}$
$endgroup$
– callculus
Dec 18 '18 at 18:43
$begingroup$
@callculus, this is what I have arrived at too. Thanks for confirming!
$endgroup$
– HFCH
Dec 18 '18 at 19:23
add a comment |
$begingroup$
I have a location problem I need help with:
Suppose a boat company wants to operate services between 11 ports in a city. The number of return journeys between port i and port j is denoted by a x-variable (Xij), i and j = 1 to 11. Now I need to impose a constraint such that the number of return journeys between the same pair of ports does not exceed 3. That is, e.g. there can be at most 3 return journeys made between port 1 and port 2.
I know I can do it by Xij + Xji <= 3, but this would result in tons of constraints...
Can anyone come up with a compact form of this constraint? Thank you in advance!
linear-programming integer-programming
asked Dec 18 '18 at 11:47
HFCHHFCH
83
$endgroup$
I have a location problem I need help with:
Suppose a boat company wants to operate services between 11 ports in a city. The number of return journeys between port i and port j is denoted by a x-variable (Xij), i and j = 1 to 11. Now I need to impose a constraint such that the number of return journeys between the same pair of ports does not exceed 3. That is, e.g. there can be at most 3 return journeys made between port 1 and port 2.
I know I can do it by Xij + Xji <= 3, but this would result in tons of constraints...
Can anyone come up with a compact form of this constraint? Thank you in advance!
linear-programming integer-programming
linear-programming integer-programming
asked Dec 18 '18 at 11:47
HFCHHFCH
83
asked Dec 18 '18 at 11:47
HFCHHFCH
83
asked Dec 18 '18 at 11:47
HFCHHFCH
83
asked Dec 18 '18 at 11:47
HFCHHFCH
83
asked Dec 18 '18 at 11:47
HFCHHFCH
83
83
$begingroup$
an alternative is Benders' decomposition, but I'd rather add those 55 constraints
$endgroup$
– LinAlg
Dec 18 '18 at 17:55
$begingroup$
Think I'd rather do the same as well and keep it simple, thanks!
$endgroup$
– HFCH
Dec 18 '18 at 18:08
$begingroup$
It is just one line: $large{x_{ij}+x_{ji}leq 3 forall i,jin {1,2, ldots , 11}}$
$endgroup$
– callculus
Dec 18 '18 at 18:43
$begingroup$
@callculus, this is what I have arrived at too. Thanks for confirming!
$endgroup$
– HFCH
Dec 18 '18 at 19:23
add a comment |
$begingroup$
an alternative is Benders' decomposition, but I'd rather add those 55 constraints
$endgroup$
– LinAlg
Dec 18 '18 at 17:55
$begingroup$
Think I'd rather do the same as well and keep it simple, thanks!
$endgroup$
– HFCH
Dec 18 '18 at 18:08
$begingroup$
It is just one line: $large{x_{ij}+x_{ji}leq 3 forall i,jin {1,2, ldots , 11}}$
$endgroup$
– callculus
Dec 18 '18 at 18:43
$begingroup$
@callculus, this is what I have arrived at too. Thanks for confirming!
$endgroup$
– HFCH
Dec 18 '18 at 19:23
$begingroup$
an alternative is Benders' decomposition, but I'd rather add those 55 constraints
$endgroup$
– LinAlg
Dec 18 '18 at 17:55
$begingroup$
an alternative is Benders' decomposition, but I'd rather add those 55 constraints
$endgroup$
– LinAlg
Dec 18 '18 at 17:55
$begingroup$
Think I'd rather do the same as well and keep it simple, thanks!
$endgroup$
– HFCH
Dec 18 '18 at 18:08
$begingroup$
Think I'd rather do the same as well and keep it simple, thanks!
$endgroup$
– HFCH
Dec 18 '18 at 18:08
$begingroup$
It is just one line: $large{x_{ij}+x_{ji}leq 3 forall i,jin {1,2, ldots , 11}}$
$endgroup$
– callculus
Dec 18 '18 at 18:43
$begingroup$
It is just one line: $large{x_{ij}+x_{ji}leq 3 forall i,jin {1,2, ldots , 11}}$
$endgroup$
– callculus
Dec 18 '18 at 18:43
$begingroup$
@callculus, this is what I have arrived at too. Thanks for confirming!
$endgroup$
– HFCH
Dec 18 '18 at 19:23
$begingroup$
@callculus, this is what I have arrived at too. Thanks for confirming!
$endgroup$
– HFCH
Dec 18 '18 at 19:23
add a comment |
0
active
oldest
votes
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%2f3045069%2flocation-problem-linear-programming%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3045069%2flocation-problem-linear-programming%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
$begingroup$
an alternative is Benders' decomposition, but I'd rather add those 55 constraints
$endgroup$
– LinAlg
Dec 18 '18 at 17:55
$begingroup$
Think I'd rather do the same as well and keep it simple, thanks!
$endgroup$
– HFCH
Dec 18 '18 at 18:08
$begingroup$
It is just one line: $large{x_{ij}+x_{ji}leq 3 forall i,jin {1,2, ldots , 11}}$
$endgroup$
– callculus
Dec 18 '18 at 18:43
$begingroup$
@callculus, this is what I have arrived at too. Thanks for confirming!
$endgroup$
– HFCH
Dec 18 '18 at 19:23