Linear Programming - Creating a sequence
$begingroup$
I have some numbers in an array and i want to model a LP problem that generates the absolute sequence of the numbers (according to their growing order).
For example
input [4,2,1,5] ---> output [3,2,1,4]
That is,if i sort [4,2,1,5], 4 has the third position, 2 is at the second position, and so on.
Can you help me ?
linear-programming
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
$endgroup$
|
show 2 more comments
$begingroup$
I have some numbers in an array and i want to model a LP problem that generates the absolute sequence of the numbers (according to their growing order).
For example
input [4,2,1,5] ---> output [3,2,1,4]
That is,if i sort [4,2,1,5], 4 has the third position, 2 is at the second position, and so on.
Can you help me ?
linear-programming
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
$endgroup$
$begingroup$
this is impossible without adding binary variables
$endgroup$
– LinAlg
Dec 27 '18 at 23:48
$begingroup$
Okay, can you show me the model with the introduction of the binary variables ?
$endgroup$
– Jhdoe
Dec 28 '18 at 7:31
$begingroup$
Why do you want to use linear programming for this task?
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
Qoute from Wikipedia: "LP is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships". I might be stupid but I don't see any connection between this problem and LP.
$endgroup$
– Oldboy
Dec 28 '18 at 8:23
$begingroup$
It's for didactic reasons. I would like to know if it's possible to do it...
$endgroup$
– Jhdoe
Dec 28 '18 at 11:53
|
show 2 more comments
$begingroup$
I have some numbers in an array and i want to model a LP problem that generates the absolute sequence of the numbers (according to their growing order).
For example
input [4,2,1,5] ---> output [3,2,1,4]
That is,if i sort [4,2,1,5], 4 has the third position, 2 is at the second position, and so on.
Can you help me ?
linear-programming
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
$endgroup$
I have some numbers in an array and i want to model a LP problem that generates the absolute sequence of the numbers (according to their growing order).
For example
input [4,2,1,5] ---> output [3,2,1,4]
That is,if i sort [4,2,1,5], 4 has the third position, 2 is at the second position, and so on.
Can you help me ?
linear-programming
linear-programming
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
asked Dec 27 '18 at 17:23
JhdoeJhdoe
517
517
$begingroup$
this is impossible without adding binary variables
$endgroup$
– LinAlg
Dec 27 '18 at 23:48
$begingroup$
Okay, can you show me the model with the introduction of the binary variables ?
$endgroup$
– Jhdoe
Dec 28 '18 at 7:31
$begingroup$
Why do you want to use linear programming for this task?
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
Qoute from Wikipedia: "LP is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships". I might be stupid but I don't see any connection between this problem and LP.
$endgroup$
– Oldboy
Dec 28 '18 at 8:23
$begingroup$
It's for didactic reasons. I would like to know if it's possible to do it...
$endgroup$
– Jhdoe
Dec 28 '18 at 11:53
|
show 2 more comments
$begingroup$
this is impossible without adding binary variables
$endgroup$
– LinAlg
Dec 27 '18 at 23:48
$begingroup$
Okay, can you show me the model with the introduction of the binary variables ?
$endgroup$
– Jhdoe
Dec 28 '18 at 7:31
$begingroup$
Why do you want to use linear programming for this task?
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
Qoute from Wikipedia: "LP is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships". I might be stupid but I don't see any connection between this problem and LP.
$endgroup$
– Oldboy
Dec 28 '18 at 8:23
$begingroup$
It's for didactic reasons. I would like to know if it's possible to do it...
$endgroup$
– Jhdoe
Dec 28 '18 at 11:53
$begingroup$
this is impossible without adding binary variables
$endgroup$
– LinAlg
Dec 27 '18 at 23:48
$begingroup$
this is impossible without adding binary variables
$endgroup$
– LinAlg
Dec 27 '18 at 23:48
$begingroup$
Okay, can you show me the model with the introduction of the binary variables ?
$endgroup$
– Jhdoe
Dec 28 '18 at 7:31
$begingroup$
Okay, can you show me the model with the introduction of the binary variables ?
$endgroup$
– Jhdoe
Dec 28 '18 at 7:31
$begingroup$
Why do you want to use linear programming for this task?
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
Why do you want to use linear programming for this task?
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
Qoute from Wikipedia: "LP is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships". I might be stupid but I don't see any connection between this problem and LP.
$endgroup$
– Oldboy
Dec 28 '18 at 8:23
$begingroup$
Qoute from Wikipedia: "LP is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships". I might be stupid but I don't see any connection between this problem and LP.
$endgroup$
– Oldboy
Dec 28 '18 at 8:23
$begingroup$
It's for didactic reasons. I would like to know if it's possible to do it...
$endgroup$
– Jhdoe
Dec 28 '18 at 11:53
$begingroup$
It's for didactic reasons. I would like to know if it's possible to do it...
$endgroup$
– Jhdoe
Dec 28 '18 at 11:53
|
show 2 more comments
2 Answers
2
active
oldest
votes
$begingroup$
Why is this such a big deal? It's just a few lines of code in any language. Here is a Python version that uses inefficient bubble sort, but it can be modified to use any other sorting algorithm:
def positions(lst):
n = len(lst)
index = [i for i in range(0, n)]
loc = [i + 1 for i in range(0, n)]
for i in range(0, n - 1):
for j in range(i + 1, n):
if lst[i] > lst[j]:
lst[i], lst[j] = lst[j], lst[i]
index[i], index[j] = index[j], index[i]
loc[index[i]], loc[index[j]] = i + 1, j + 1
return loc
# prints [3,2,1,4]
print(positions([4,2,1,5]))
#prints [6, 3, 1, 4, 5, 7, 8, 9, 10, 2]
print(positions([6,2,0,3,5,7,9,13,15,1]))
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
$endgroup$
$begingroup$
But OP wants to use linear programming (for some reason).
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
this is a oneliner with numpy.argsort or with sorted and a lambda function
$endgroup$
– LinAlg
Dec 28 '18 at 16:25
add a comment |
$begingroup$
Let your sequence be given as $x_{i}$ and introduce binary variables $y_{ik}$ and $z_{ij}$. The following constraints make $y_{ik}$ take the value 1 if $x_i$ is the $k$-th number in the ordered sequence, and make $z_{ij}$ take the value 1 if $x_i leq x_j$:
$$sum_i y_{ik} = 1 ; forall k$$
$$sum_k y_{ik} = 1 ; forall i$$
$$x_ileq x_j + M_1(1-z_{ij}) ; forall i,j$$
$$M_2 z_{ij} geq sum_k k y_{jk} - sum_k k y_{ik} ; forall i,j$$
Your output list is given by $(sum_k k y_{ik})_{i=1}^n$. The third constraint enforces $x_i leq x_j$, unless $z_{ij}=0$. while the last constraint forces $z_{ij}$ to take the value 1 if the ordering position of $x_i$ (which is $sum_k k y_{ik}$) is less than the ordering position of $x_j$. $M_1$ and $M_2$ are parameters that should be sufficiently large: $M_1$ should be at least the difference between the largest and the smallest $x_i$ and $M_2$ should be at least $n-1$ where $n$ is the number of elements in your list).
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
$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%2f3054181%2flinear-programming-creating-a-sequence%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
$begingroup$
Why is this such a big deal? It's just a few lines of code in any language. Here is a Python version that uses inefficient bubble sort, but it can be modified to use any other sorting algorithm:
def positions(lst):
n = len(lst)
index = [i for i in range(0, n)]
loc = [i + 1 for i in range(0, n)]
for i in range(0, n - 1):
for j in range(i + 1, n):
if lst[i] > lst[j]:
lst[i], lst[j] = lst[j], lst[i]
index[i], index[j] = index[j], index[i]
loc[index[i]], loc[index[j]] = i + 1, j + 1
return loc
# prints [3,2,1,4]
print(positions([4,2,1,5]))
#prints [6, 3, 1, 4, 5, 7, 8, 9, 10, 2]
print(positions([6,2,0,3,5,7,9,13,15,1]))
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
$endgroup$
$begingroup$
But OP wants to use linear programming (for some reason).
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
this is a oneliner with numpy.argsort or with sorted and a lambda function
$endgroup$
– LinAlg
Dec 28 '18 at 16:25
add a comment |
$begingroup$
Why is this such a big deal? It's just a few lines of code in any language. Here is a Python version that uses inefficient bubble sort, but it can be modified to use any other sorting algorithm:
def positions(lst):
n = len(lst)
index = [i for i in range(0, n)]
loc = [i + 1 for i in range(0, n)]
for i in range(0, n - 1):
for j in range(i + 1, n):
if lst[i] > lst[j]:
lst[i], lst[j] = lst[j], lst[i]
index[i], index[j] = index[j], index[i]
loc[index[i]], loc[index[j]] = i + 1, j + 1
return loc
# prints [3,2,1,4]
print(positions([4,2,1,5]))
#prints [6, 3, 1, 4, 5, 7, 8, 9, 10, 2]
print(positions([6,2,0,3,5,7,9,13,15,1]))
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
$endgroup$
$begingroup$
But OP wants to use linear programming (for some reason).
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
this is a oneliner with numpy.argsort or with sorted and a lambda function
$endgroup$
– LinAlg
Dec 28 '18 at 16:25
add a comment |
$begingroup$
Why is this such a big deal? It's just a few lines of code in any language. Here is a Python version that uses inefficient bubble sort, but it can be modified to use any other sorting algorithm:
def positions(lst):
n = len(lst)
index = [i for i in range(0, n)]
loc = [i + 1 for i in range(0, n)]
for i in range(0, n - 1):
for j in range(i + 1, n):
if lst[i] > lst[j]:
lst[i], lst[j] = lst[j], lst[i]
index[i], index[j] = index[j], index[i]
loc[index[i]], loc[index[j]] = i + 1, j + 1
return loc
# prints [3,2,1,4]
print(positions([4,2,1,5]))
#prints [6, 3, 1, 4, 5, 7, 8, 9, 10, 2]
print(positions([6,2,0,3,5,7,9,13,15,1]))
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
$endgroup$
Why is this such a big deal? It's just a few lines of code in any language. Here is a Python version that uses inefficient bubble sort, but it can be modified to use any other sorting algorithm:
def positions(lst):
n = len(lst)
index = [i for i in range(0, n)]
loc = [i + 1 for i in range(0, n)]
for i in range(0, n - 1):
for j in range(i + 1, n):
if lst[i] > lst[j]:
lst[i], lst[j] = lst[j], lst[i]
index[i], index[j] = index[j], index[i]
loc[index[i]], loc[index[j]] = i + 1, j + 1
return loc
# prints [3,2,1,4]
print(positions([4,2,1,5]))
#prints [6, 3, 1, 4, 5, 7, 8, 9, 10, 2]
print(positions([6,2,0,3,5,7,9,13,15,1]))
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
answered Dec 28 '18 at 7:57
OldboyOldboy
8,85611138
8,85611138
$begingroup$
But OP wants to use linear programming (for some reason).
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
this is a oneliner with numpy.argsort or with sorted and a lambda function
$endgroup$
– LinAlg
Dec 28 '18 at 16:25
add a comment |
$begingroup$
But OP wants to use linear programming (for some reason).
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
this is a oneliner with numpy.argsort or with sorted and a lambda function
$endgroup$
– LinAlg
Dec 28 '18 at 16:25
$begingroup$
But OP wants to use linear programming (for some reason).
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
But OP wants to use linear programming (for some reason).
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
this is a oneliner with numpy.argsort or with sorted and a lambda function
$endgroup$
– LinAlg
Dec 28 '18 at 16:25
$begingroup$
this is a oneliner with numpy.argsort or with sorted and a lambda function
$endgroup$
– LinAlg
Dec 28 '18 at 16:25
add a comment |
$begingroup$
Let your sequence be given as $x_{i}$ and introduce binary variables $y_{ik}$ and $z_{ij}$. The following constraints make $y_{ik}$ take the value 1 if $x_i$ is the $k$-th number in the ordered sequence, and make $z_{ij}$ take the value 1 if $x_i leq x_j$:
$$sum_i y_{ik} = 1 ; forall k$$
$$sum_k y_{ik} = 1 ; forall i$$
$$x_ileq x_j + M_1(1-z_{ij}) ; forall i,j$$
$$M_2 z_{ij} geq sum_k k y_{jk} - sum_k k y_{ik} ; forall i,j$$
Your output list is given by $(sum_k k y_{ik})_{i=1}^n$. The third constraint enforces $x_i leq x_j$, unless $z_{ij}=0$. while the last constraint forces $z_{ij}$ to take the value 1 if the ordering position of $x_i$ (which is $sum_k k y_{ik}$) is less than the ordering position of $x_j$. $M_1$ and $M_2$ are parameters that should be sufficiently large: $M_1$ should be at least the difference between the largest and the smallest $x_i$ and $M_2$ should be at least $n-1$ where $n$ is the number of elements in your list).
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
$endgroup$
add a comment |
$begingroup$
Let your sequence be given as $x_{i}$ and introduce binary variables $y_{ik}$ and $z_{ij}$. The following constraints make $y_{ik}$ take the value 1 if $x_i$ is the $k$-th number in the ordered sequence, and make $z_{ij}$ take the value 1 if $x_i leq x_j$:
$$sum_i y_{ik} = 1 ; forall k$$
$$sum_k y_{ik} = 1 ; forall i$$
$$x_ileq x_j + M_1(1-z_{ij}) ; forall i,j$$
$$M_2 z_{ij} geq sum_k k y_{jk} - sum_k k y_{ik} ; forall i,j$$
Your output list is given by $(sum_k k y_{ik})_{i=1}^n$. The third constraint enforces $x_i leq x_j$, unless $z_{ij}=0$. while the last constraint forces $z_{ij}$ to take the value 1 if the ordering position of $x_i$ (which is $sum_k k y_{ik}$) is less than the ordering position of $x_j$. $M_1$ and $M_2$ are parameters that should be sufficiently large: $M_1$ should be at least the difference between the largest and the smallest $x_i$ and $M_2$ should be at least $n-1$ where $n$ is the number of elements in your list).
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
$endgroup$
add a comment |
$begingroup$
Let your sequence be given as $x_{i}$ and introduce binary variables $y_{ik}$ and $z_{ij}$. The following constraints make $y_{ik}$ take the value 1 if $x_i$ is the $k$-th number in the ordered sequence, and make $z_{ij}$ take the value 1 if $x_i leq x_j$:
$$sum_i y_{ik} = 1 ; forall k$$
$$sum_k y_{ik} = 1 ; forall i$$
$$x_ileq x_j + M_1(1-z_{ij}) ; forall i,j$$
$$M_2 z_{ij} geq sum_k k y_{jk} - sum_k k y_{ik} ; forall i,j$$
Your output list is given by $(sum_k k y_{ik})_{i=1}^n$. The third constraint enforces $x_i leq x_j$, unless $z_{ij}=0$. while the last constraint forces $z_{ij}$ to take the value 1 if the ordering position of $x_i$ (which is $sum_k k y_{ik}$) is less than the ordering position of $x_j$. $M_1$ and $M_2$ are parameters that should be sufficiently large: $M_1$ should be at least the difference between the largest and the smallest $x_i$ and $M_2$ should be at least $n-1$ where $n$ is the number of elements in your list).
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
$endgroup$
Let your sequence be given as $x_{i}$ and introduce binary variables $y_{ik}$ and $z_{ij}$. The following constraints make $y_{ik}$ take the value 1 if $x_i$ is the $k$-th number in the ordered sequence, and make $z_{ij}$ take the value 1 if $x_i leq x_j$:
$$sum_i y_{ik} = 1 ; forall k$$
$$sum_k y_{ik} = 1 ; forall i$$
$$x_ileq x_j + M_1(1-z_{ij}) ; forall i,j$$
$$M_2 z_{ij} geq sum_k k y_{jk} - sum_k k y_{ik} ; forall i,j$$
Your output list is given by $(sum_k k y_{ik})_{i=1}^n$. The third constraint enforces $x_i leq x_j$, unless $z_{ij}=0$. while the last constraint forces $z_{ij}$ to take the value 1 if the ordering position of $x_i$ (which is $sum_k k y_{ik}$) is less than the ordering position of $x_j$. $M_1$ and $M_2$ are parameters that should be sufficiently large: $M_1$ should be at least the difference between the largest and the smallest $x_i$ and $M_2$ should be at least $n-1$ where $n$ is the number of elements in your list).
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
edited Dec 28 '18 at 14:08
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
answered Dec 28 '18 at 13:57
LinAlgLinAlg
10.1k1521
10.1k1521
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%2f3054181%2flinear-programming-creating-a-sequence%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$
this is impossible without adding binary variables
$endgroup$
– LinAlg
Dec 27 '18 at 23:48
$begingroup$
Okay, can you show me the model with the introduction of the binary variables ?
$endgroup$
– Jhdoe
Dec 28 '18 at 7:31
$begingroup$
Why do you want to use linear programming for this task?
$endgroup$
– littleO
Dec 28 '18 at 8:06
$begingroup$
Qoute from Wikipedia: "LP is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships". I might be stupid but I don't see any connection between this problem and LP.
$endgroup$
– Oldboy
Dec 28 '18 at 8:23
$begingroup$
It's for didactic reasons. I would like to know if it's possible to do it...
$endgroup$
– Jhdoe
Dec 28 '18 at 11:53