Removing redundant linear constraints using Gaussian elimination
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I have a set of linear constraints in the form of $c_i x ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set.
Here I found a similar question, however it is not clear to me how to use Gaussian elimination to identify the redundant constraint.
Do you have any hints on this?
linear-algebra linear-programming gaussian-elimination
add a comment |Â
up vote
3
down vote
favorite
I have a set of linear constraints in the form of $c_i x ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set.
Here I found a similar question, however it is not clear to me how to use Gaussian elimination to identify the redundant constraint.
Do you have any hints on this?
linear-algebra linear-programming gaussian-elimination
1
I'm not sure but you can find the rank of $C$ (of $Cxgeq d$) and then append the new constraint at the bottom of $C$ to form $C^*$ and find the rank of $C^*xgeq d^*$. Rank can be found by RREF which is esentially Gauss Elimination.
â Inquest
Nov 11 '12 at 20:19
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
â amWhy
Nov 11 '12 at 21:01
amWhy: Sure, thanks for your help
â Jack
Nov 11 '12 at 21:04
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I have a set of linear constraints in the form of $c_i x ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set.
Here I found a similar question, however it is not clear to me how to use Gaussian elimination to identify the redundant constraint.
Do you have any hints on this?
linear-algebra linear-programming gaussian-elimination
I have a set of linear constraints in the form of $c_i x ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set.
Here I found a similar question, however it is not clear to me how to use Gaussian elimination to identify the redundant constraint.
Do you have any hints on this?
linear-algebra linear-programming gaussian-elimination
edited Aug 3 '17 at 13:01
Rodrigo de Azevedo
12.6k41751
12.6k41751
asked Nov 11 '12 at 20:11
Jack
336
336
1
I'm not sure but you can find the rank of $C$ (of $Cxgeq d$) and then append the new constraint at the bottom of $C$ to form $C^*$ and find the rank of $C^*xgeq d^*$. Rank can be found by RREF which is esentially Gauss Elimination.
â Inquest
Nov 11 '12 at 20:19
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
â amWhy
Nov 11 '12 at 21:01
amWhy: Sure, thanks for your help
â Jack
Nov 11 '12 at 21:04
add a comment |Â
1
I'm not sure but you can find the rank of $C$ (of $Cxgeq d$) and then append the new constraint at the bottom of $C$ to form $C^*$ and find the rank of $C^*xgeq d^*$. Rank can be found by RREF which is esentially Gauss Elimination.
â Inquest
Nov 11 '12 at 20:19
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
â amWhy
Nov 11 '12 at 21:01
amWhy: Sure, thanks for your help
â Jack
Nov 11 '12 at 21:04
1
1
I'm not sure but you can find the rank of $C$ (of $Cxgeq d$) and then append the new constraint at the bottom of $C$ to form $C^*$ and find the rank of $C^*xgeq d^*$. Rank can be found by RREF which is esentially Gauss Elimination.
â Inquest
Nov 11 '12 at 20:19
I'm not sure but you can find the rank of $C$ (of $Cxgeq d$) and then append the new constraint at the bottom of $C$ to form $C^*$ and find the rank of $C^*xgeq d^*$. Rank can be found by RREF which is esentially Gauss Elimination.
â Inquest
Nov 11 '12 at 20:19
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
â amWhy
Nov 11 '12 at 21:01
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
â amWhy
Nov 11 '12 at 21:01
amWhy: Sure, thanks for your help
â Jack
Nov 11 '12 at 21:04
amWhy: Sure, thanks for your help
â Jack
Nov 11 '12 at 21:04
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
See my answer to this MO question.
Hi, this is what I am currently doing. However I am writing a piece of software that "frequently" invokes the constraint detection and I found that solving a linear problem is slow and can get stuck in lots of iterations while finding the optimal solution (which happens a lot with higher dimensions).
â Jack
Nov 11 '12 at 20:46
I was hoping that being that the Simplex method is based on Gauss Elimination, maybe there was a simplified version of it to remove redundant constraints...
â Jack
Nov 11 '12 at 20:47
add a comment |Â
up vote
0
down vote
You might be interested in reading about "pruning constraints" which is discussed in chapter 11 (entitled "Analytic center cutting plane-method") of Vandenberghe's 236c notes. See slide 11-12 ("pruning constraints").
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
See my answer to this MO question.
Hi, this is what I am currently doing. However I am writing a piece of software that "frequently" invokes the constraint detection and I found that solving a linear problem is slow and can get stuck in lots of iterations while finding the optimal solution (which happens a lot with higher dimensions).
â Jack
Nov 11 '12 at 20:46
I was hoping that being that the Simplex method is based on Gauss Elimination, maybe there was a simplified version of it to remove redundant constraints...
â Jack
Nov 11 '12 at 20:47
add a comment |Â
up vote
0
down vote
See my answer to this MO question.
Hi, this is what I am currently doing. However I am writing a piece of software that "frequently" invokes the constraint detection and I found that solving a linear problem is slow and can get stuck in lots of iterations while finding the optimal solution (which happens a lot with higher dimensions).
â Jack
Nov 11 '12 at 20:46
I was hoping that being that the Simplex method is based on Gauss Elimination, maybe there was a simplified version of it to remove redundant constraints...
â Jack
Nov 11 '12 at 20:47
add a comment |Â
up vote
0
down vote
up vote
0
down vote
See my answer to this MO question.
See my answer to this MO question.
edited Apr 13 '17 at 12:58
Communityâ¦
1
1
answered Nov 11 '12 at 20:24
Tony Huynh
81057
81057
Hi, this is what I am currently doing. However I am writing a piece of software that "frequently" invokes the constraint detection and I found that solving a linear problem is slow and can get stuck in lots of iterations while finding the optimal solution (which happens a lot with higher dimensions).
â Jack
Nov 11 '12 at 20:46
I was hoping that being that the Simplex method is based on Gauss Elimination, maybe there was a simplified version of it to remove redundant constraints...
â Jack
Nov 11 '12 at 20:47
add a comment |Â
Hi, this is what I am currently doing. However I am writing a piece of software that "frequently" invokes the constraint detection and I found that solving a linear problem is slow and can get stuck in lots of iterations while finding the optimal solution (which happens a lot with higher dimensions).
â Jack
Nov 11 '12 at 20:46
I was hoping that being that the Simplex method is based on Gauss Elimination, maybe there was a simplified version of it to remove redundant constraints...
â Jack
Nov 11 '12 at 20:47
Hi, this is what I am currently doing. However I am writing a piece of software that "frequently" invokes the constraint detection and I found that solving a linear problem is slow and can get stuck in lots of iterations while finding the optimal solution (which happens a lot with higher dimensions).
â Jack
Nov 11 '12 at 20:46
Hi, this is what I am currently doing. However I am writing a piece of software that "frequently" invokes the constraint detection and I found that solving a linear problem is slow and can get stuck in lots of iterations while finding the optimal solution (which happens a lot with higher dimensions).
â Jack
Nov 11 '12 at 20:46
I was hoping that being that the Simplex method is based on Gauss Elimination, maybe there was a simplified version of it to remove redundant constraints...
â Jack
Nov 11 '12 at 20:47
I was hoping that being that the Simplex method is based on Gauss Elimination, maybe there was a simplified version of it to remove redundant constraints...
â Jack
Nov 11 '12 at 20:47
add a comment |Â
up vote
0
down vote
You might be interested in reading about "pruning constraints" which is discussed in chapter 11 (entitled "Analytic center cutting plane-method") of Vandenberghe's 236c notes. See slide 11-12 ("pruning constraints").
add a comment |Â
up vote
0
down vote
You might be interested in reading about "pruning constraints" which is discussed in chapter 11 (entitled "Analytic center cutting plane-method") of Vandenberghe's 236c notes. See slide 11-12 ("pruning constraints").
add a comment |Â
up vote
0
down vote
up vote
0
down vote
You might be interested in reading about "pruning constraints" which is discussed in chapter 11 (entitled "Analytic center cutting plane-method") of Vandenberghe's 236c notes. See slide 11-12 ("pruning constraints").
You might be interested in reading about "pruning constraints" which is discussed in chapter 11 (entitled "Analytic center cutting plane-method") of Vandenberghe's 236c notes. See slide 11-12 ("pruning constraints").
answered Nov 13 '12 at 10:51
littleO
26.3k540102
26.3k540102
add a comment |Â
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%2f235126%2fremoving-redundant-linear-constraints-using-gaussian-elimination%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
1
I'm not sure but you can find the rank of $C$ (of $Cxgeq d$) and then append the new constraint at the bottom of $C$ to form $C^*$ and find the rank of $C^*xgeq d^*$. Rank can be found by RREF which is esentially Gauss Elimination.
â Inquest
Nov 11 '12 at 20:19
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
â amWhy
Nov 11 '12 at 21:01
amWhy: Sure, thanks for your help
â Jack
Nov 11 '12 at 21:04