Rank-dependent constraints in linear programming
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
I have a typical linear optimization problem:
$c'x to max_x$
s.t. $~~l leq Ax leq u,$
where $x = (x_1, ...,x_n)'$, $A - k times n$ matrix of constraints coefficient, $l$ and $u$ are $k times 1$ vectors of lower and upper bounds, respectively.
I need to add specific constraints on $i$-th largest element in vector $x$:
$x_(i) leq b_i, ~~ i = 1...n$,
where $x_(1) geq x_(2) geq ... geq x_(n)$.
In other words, each variable's individual bound depends on its rank. Is there a way to reformulate it as an LP constraint?
optimization linear-programming constraints
asked Aug 9 at 15:10
user10203644
31
add a comment |Â
up vote
0
down vote
favorite
I have a typical linear optimization problem:
$c'x to max_x$
s.t. $~~l leq Ax leq u,$
where $x = (x_1, ...,x_n)'$, $A - k times n$ matrix of constraints coefficient, $l$ and $u$ are $k times 1$ vectors of lower and upper bounds, respectively.
I need to add specific constraints on $i$-th largest element in vector $x$:
$x_(i) leq b_i, ~~ i = 1...n$,
where $x_(1) geq x_(2) geq ... geq x_(n)$.
In other words, each variable's individual bound depends on its rank. Is there a way to reformulate it as an LP constraint?
optimization linear-programming constraints
asked Aug 9 at 15:10
user10203644
31
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
I have a typical linear optimization problem:
$c'x to max_x$
s.t. $~~l leq Ax leq u,$
where $x = (x_1, ...,x_n)'$, $A - k times n$ matrix of constraints coefficient, $l$ and $u$ are $k times 1$ vectors of lower and upper bounds, respectively.
I need to add specific constraints on $i$-th largest element in vector $x$:
$x_(i) leq b_i, ~~ i = 1...n$,
where $x_(1) geq x_(2) geq ... geq x_(n)$.
In other words, each variable's individual bound depends on its rank. Is there a way to reformulate it as an LP constraint?
optimization linear-programming constraints
asked Aug 9 at 15:10
user10203644
31
I have a typical linear optimization problem:
$c'x to max_x$
s.t. $~~l leq Ax leq u,$
where $x = (x_1, ...,x_n)'$, $A - k times n$ matrix of constraints coefficient, $l$ and $u$ are $k times 1$ vectors of lower and upper bounds, respectively.
I need to add specific constraints on $i$-th largest element in vector $x$:
$x_(i) leq b_i, ~~ i = 1...n$,
where $x_(1) geq x_(2) geq ... geq x_(n)$.
In other words, each variable's individual bound depends on its rank. Is there a way to reformulate it as an LP constraint?
optimization linear-programming constraints
asked Aug 9 at 15:10
user10203644
31
asked Aug 9 at 15:10
user10203644
31
asked Aug 9 at 15:10
user10203644
31
asked Aug 9 at 15:10
user10203644
31
31
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
By setting the first $n-1$ values of $b$ to $infty$, you would effectively have a method to implement $min x leq b_n$, which isn't LP-representable as $min$ is concave. Hence, not possible.
Constraining the sum of the $k$ largest elements is LP-representable though (and your constraint is mixed-integer LP-representable).
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example?
– user10203644
Aug 10 at 14:41
The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i geq s_i-1$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages.
– Johan Löfberg
Aug 10 at 20:29
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
By setting the first $n-1$ values of $b$ to $infty$, you would effectively have a method to implement $min x leq b_n$, which isn't LP-representable as $min$ is concave. Hence, not possible.
Constraining the sum of the $k$ largest elements is LP-representable though (and your constraint is mixed-integer LP-representable).
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example?
– user10203644
Aug 10 at 14:41
The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i geq s_i-1$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages.
– Johan Löfberg
Aug 10 at 20:29
add a comment |Â
up vote
1
down vote
accepted
By setting the first $n-1$ values of $b$ to $infty$, you would effectively have a method to implement $min x leq b_n$, which isn't LP-representable as $min$ is concave. Hence, not possible.
Constraining the sum of the $k$ largest elements is LP-representable though (and your constraint is mixed-integer LP-representable).
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example?
– user10203644
Aug 10 at 14:41
The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i geq s_i-1$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages.
– Johan Löfberg
Aug 10 at 20:29
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
By setting the first $n-1$ values of $b$ to $infty$, you would effectively have a method to implement $min x leq b_n$, which isn't LP-representable as $min$ is concave. Hence, not possible.
Constraining the sum of the $k$ largest elements is LP-representable though (and your constraint is mixed-integer LP-representable).
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
By setting the first $n-1$ values of $b$ to $infty$, you would effectively have a method to implement $min x leq b_n$, which isn't LP-representable as $min$ is concave. Hence, not possible.
Constraining the sum of the $k$ largest elements is LP-representable though (and your constraint is mixed-integer LP-representable).
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
answered Aug 9 at 18:59
Johan Löfberg
4,6921811
4,6921811
Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example?
– user10203644
Aug 10 at 14:41
The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i geq s_i-1$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages.
– Johan Löfberg
Aug 10 at 20:29
add a comment |Â
Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example?
– user10203644
Aug 10 at 14:41
The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i geq s_i-1$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages.
– Johan Löfberg
Aug 10 at 20:29
Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example?
– user10203644
Aug 10 at 14:41
Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example?
– user10203644
Aug 10 at 14:41
The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i geq s_i-1$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages.
– Johan Löfberg
Aug 10 at 20:29
The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i geq s_i-1$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages.
– Johan Löfberg
Aug 10 at 20:29
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2877301%2frank-dependent-constraints-in-linear-programming%23new-answer', 'question_page');
);
Post as a guest
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
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
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
