Removing redundant linear constraints using Gaussian elimination

The name of the pictureThe name of the pictureThe name of the pictureClash 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?







share|cite|improve this question


















  • 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














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?







share|cite|improve this question


















  • 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












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?







share|cite|improve this question














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?









share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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












  • 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










2 Answers
2






active

oldest

votes

















up vote
0
down vote













See my answer to this MO question.






share|cite|improve this answer






















  • 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

















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").






share|cite|improve this answer




















    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',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );








     

    draft saved


    draft discarded


















    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






























    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.






    share|cite|improve this answer






















    • 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














    up vote
    0
    down vote













    See my answer to this MO question.






    share|cite|improve this answer






















    • 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












    up vote
    0
    down vote










    up vote
    0
    down vote









    See my answer to this MO question.






    share|cite|improve this answer














    See my answer to this MO question.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    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
















    • 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










    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").






    share|cite|improve this answer
























      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").






      share|cite|improve this answer






















        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").






        share|cite|improve this answer












        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").







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Nov 13 '12 at 10:51









        littleO

        26.3k540102




        26.3k540102






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            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













































































            這個網誌中的熱門文章

            How to combine Bézier curves to a surface?

            Mutual Information Always Non-negative

            Why am i infinitely getting the same tweet with the Twitter Search API?