Linear program for way optimization with unusual constraints
$begingroup$
I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com:
The goal of the game is to pick up all the animals and return them to their houses, by driving the car. The distance, from object (= {Point, Animal, House}) to object is always 1. You can only drive on roads. You are allowed to pass an animal without picking it up. The car's capacity for animals is 4. Find a quickest route. (In the game your gas is limited (25 in the picture) which corresponds to the optimal distance.)
Can this problem be formulated as a linear program? And if so, how? Does this kind of problem have a name?
My fist idea was to do a network with edge cost. Then I thought about the traveling salesman problem, or a transportation problem, or a flow problem, but they don't quite fit.
My best ansatz so far is this:
An s-t-flow network for every animal, where there is an in and an out edge for every connection. A flow network for the car, where only the source is defined.
Let $x_{i,j,k}$ be the number of times animal $kin{1,...,n}$ is transported from node i to node j.
Let $x_{i,j,0}$ be the number of times the car drives from node i to node j.
Let $s_k$ be animal k's node, and $t_k$ be animal k's home node.
Let $s_0$ the car's node.
From the s-t-flow networks follows:
$sum_i x_{l,i,k}-x_{i,l,k}=0,forall lnotin{s_k,t_k},forall kin{1,...,n}$
$sum_i x_{s_k,i,k}-x_{i,s_k,k}=1,forall kin{1,...,n}$
$sum_i x_{t_k,i,k}-x_{i,t_k,k}=-1,forall kin{1,...,n}$
$x_{i,j,k} in mathbb{N}_0, forall i,j,k$
Since an animal can't travel without the car:
$x_{i,j,0} geq x_{i,j,k}, forall kin{1,...,n}$
And thus the objective becomes: min $sum_{i,j} x_{i,j,0}$
The restrictions for the car:
$sum_i x_{l,i,0}-x_{i,l,0}leq 0,forall lnotin{s_0}$
$sum_i x_{s_0,i,0}-x_{i,s_0,0}=-1$
Now all that is missing, is the restriction on the car's capacity. How would one do that?
linear-programming
edited Mar 9 '17 at 17:32
Community♦
1
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
$endgroup$
add a comment |
$begingroup$
I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com:
The goal of the game is to pick up all the animals and return them to their houses, by driving the car. The distance, from object (= {Point, Animal, House}) to object is always 1. You can only drive on roads. You are allowed to pass an animal without picking it up. The car's capacity for animals is 4. Find a quickest route. (In the game your gas is limited (25 in the picture) which corresponds to the optimal distance.)
Can this problem be formulated as a linear program? And if so, how? Does this kind of problem have a name?
My fist idea was to do a network with edge cost. Then I thought about the traveling salesman problem, or a transportation problem, or a flow problem, but they don't quite fit.
My best ansatz so far is this:
An s-t-flow network for every animal, where there is an in and an out edge for every connection. A flow network for the car, where only the source is defined.
Let $x_{i,j,k}$ be the number of times animal $kin{1,...,n}$ is transported from node i to node j.
Let $x_{i,j,0}$ be the number of times the car drives from node i to node j.
Let $s_k$ be animal k's node, and $t_k$ be animal k's home node.
Let $s_0$ the car's node.
From the s-t-flow networks follows:
$sum_i x_{l,i,k}-x_{i,l,k}=0,forall lnotin{s_k,t_k},forall kin{1,...,n}$
$sum_i x_{s_k,i,k}-x_{i,s_k,k}=1,forall kin{1,...,n}$
$sum_i x_{t_k,i,k}-x_{i,t_k,k}=-1,forall kin{1,...,n}$
$x_{i,j,k} in mathbb{N}_0, forall i,j,k$
Since an animal can't travel without the car:
$x_{i,j,0} geq x_{i,j,k}, forall kin{1,...,n}$
And thus the objective becomes: min $sum_{i,j} x_{i,j,0}$
The restrictions for the car:
$sum_i x_{l,i,0}-x_{i,l,0}leq 0,forall lnotin{s_0}$
$sum_i x_{s_0,i,0}-x_{i,s_0,0}=-1$
Now all that is missing, is the restriction on the car's capacity. How would one do that?
linear-programming
edited Mar 9 '17 at 17:32
Community♦
1
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
$endgroup$
add a comment |
$begingroup$
I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com:
The goal of the game is to pick up all the animals and return them to their houses, by driving the car. The distance, from object (= {Point, Animal, House}) to object is always 1. You can only drive on roads. You are allowed to pass an animal without picking it up. The car's capacity for animals is 4. Find a quickest route. (In the game your gas is limited (25 in the picture) which corresponds to the optimal distance.)
Can this problem be formulated as a linear program? And if so, how? Does this kind of problem have a name?
My fist idea was to do a network with edge cost. Then I thought about the traveling salesman problem, or a transportation problem, or a flow problem, but they don't quite fit.
My best ansatz so far is this:
An s-t-flow network for every animal, where there is an in and an out edge for every connection. A flow network for the car, where only the source is defined.
Let $x_{i,j,k}$ be the number of times animal $kin{1,...,n}$ is transported from node i to node j.
Let $x_{i,j,0}$ be the number of times the car drives from node i to node j.
Let $s_k$ be animal k's node, and $t_k$ be animal k's home node.
Let $s_0$ the car's node.
From the s-t-flow networks follows:
$sum_i x_{l,i,k}-x_{i,l,k}=0,forall lnotin{s_k,t_k},forall kin{1,...,n}$
$sum_i x_{s_k,i,k}-x_{i,s_k,k}=1,forall kin{1,...,n}$
$sum_i x_{t_k,i,k}-x_{i,t_k,k}=-1,forall kin{1,...,n}$
$x_{i,j,k} in mathbb{N}_0, forall i,j,k$
Since an animal can't travel without the car:
$x_{i,j,0} geq x_{i,j,k}, forall kin{1,...,n}$
And thus the objective becomes: min $sum_{i,j} x_{i,j,0}$
The restrictions for the car:
$sum_i x_{l,i,0}-x_{i,l,0}leq 0,forall lnotin{s_0}$
$sum_i x_{s_0,i,0}-x_{i,s_0,0}=-1$
Now all that is missing, is the restriction on the car's capacity. How would one do that?
linear-programming
edited Mar 9 '17 at 17:32
Community♦
1
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
$endgroup$
I've just finished the lecture "Introduction to Optimization", so I know something about linear programming, and came across the following game on lumosity.com:
The goal of the game is to pick up all the animals and return them to their houses, by driving the car. The distance, from object (= {Point, Animal, House}) to object is always 1. You can only drive on roads. You are allowed to pass an animal without picking it up. The car's capacity for animals is 4. Find a quickest route. (In the game your gas is limited (25 in the picture) which corresponds to the optimal distance.)
Can this problem be formulated as a linear program? And if so, how? Does this kind of problem have a name?
My fist idea was to do a network with edge cost. Then I thought about the traveling salesman problem, or a transportation problem, or a flow problem, but they don't quite fit.
My best ansatz so far is this:
An s-t-flow network for every animal, where there is an in and an out edge for every connection. A flow network for the car, where only the source is defined.
Let $x_{i,j,k}$ be the number of times animal $kin{1,...,n}$ is transported from node i to node j.
Let $x_{i,j,0}$ be the number of times the car drives from node i to node j.
Let $s_k$ be animal k's node, and $t_k$ be animal k's home node.
Let $s_0$ the car's node.
From the s-t-flow networks follows:
$sum_i x_{l,i,k}-x_{i,l,k}=0,forall lnotin{s_k,t_k},forall kin{1,...,n}$
$sum_i x_{s_k,i,k}-x_{i,s_k,k}=1,forall kin{1,...,n}$
$sum_i x_{t_k,i,k}-x_{i,t_k,k}=-1,forall kin{1,...,n}$
$x_{i,j,k} in mathbb{N}_0, forall i,j,k$
Since an animal can't travel without the car:
$x_{i,j,0} geq x_{i,j,k}, forall kin{1,...,n}$
And thus the objective becomes: min $sum_{i,j} x_{i,j,0}$
The restrictions for the car:
$sum_i x_{l,i,0}-x_{i,l,0}leq 0,forall lnotin{s_0}$
$sum_i x_{s_0,i,0}-x_{i,s_0,0}=-1$
Now all that is missing, is the restriction on the car's capacity. How would one do that?
linear-programming
linear-programming
edited Mar 9 '17 at 17:32
Community♦
1
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
edited Mar 9 '17 at 17:32
Community♦
1
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
edited Mar 9 '17 at 17:32
Community♦
1
edited Mar 9 '17 at 17:32
Community♦
1
edited Mar 9 '17 at 17:32
Community♦
1
1
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
asked Jan 24 '15 at 14:32
Dominic HoferDominic Hofer
1214
1214
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
PanicSheep,
Regarding a solver for the Lumosity Pet Detective puzzle, I used SolverStudio for linear programming and following a 2002 reference Quan Lu and Maged Dessouky, I constructed the constraints to solve the puzzle. It's not particularly fast, but works. Files are on GitHub, reference below:
http://www.sampledsystems.com/using-solverstudio-for-linear-programming/
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
$endgroup$
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%2f1117722%2flinear-program-for-way-optimization-with-unusual-constraints%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$
PanicSheep,
Regarding a solver for the Lumosity Pet Detective puzzle, I used SolverStudio for linear programming and following a 2002 reference Quan Lu and Maged Dessouky, I constructed the constraints to solve the puzzle. It's not particularly fast, but works. Files are on GitHub, reference below:
http://www.sampledsystems.com/using-solverstudio-for-linear-programming/
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
$endgroup$
add a comment |
$begingroup$
PanicSheep,
Regarding a solver for the Lumosity Pet Detective puzzle, I used SolverStudio for linear programming and following a 2002 reference Quan Lu and Maged Dessouky, I constructed the constraints to solve the puzzle. It's not particularly fast, but works. Files are on GitHub, reference below:
http://www.sampledsystems.com/using-solverstudio-for-linear-programming/
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
$endgroup$
add a comment |
$begingroup$
PanicSheep,
Regarding a solver for the Lumosity Pet Detective puzzle, I used SolverStudio for linear programming and following a 2002 reference Quan Lu and Maged Dessouky, I constructed the constraints to solve the puzzle. It's not particularly fast, but works. Files are on GitHub, reference below:
http://www.sampledsystems.com/using-solverstudio-for-linear-programming/
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
$endgroup$
PanicSheep,
Regarding a solver for the Lumosity Pet Detective puzzle, I used SolverStudio for linear programming and following a 2002 reference Quan Lu and Maged Dessouky, I constructed the constraints to solve the puzzle. It's not particularly fast, but works. Files are on GitHub, reference below:
http://www.sampledsystems.com/using-solverstudio-for-linear-programming/
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
answered Jun 15 '17 at 16:16
PointOnePAPointOnePA
1
1
add a comment |
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%2f1117722%2flinear-program-for-way-optimization-with-unusual-constraints%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
