Removing redundant linear constraints using Gaussian elimination












3












$begingroup$


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







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    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.
    $endgroup$
    – Inquest
    Nov 11 '12 at 20:19












  • $begingroup$
    Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
    $endgroup$
    – amWhy
    Nov 11 '12 at 21:01










  • $begingroup$
    amWhy: Sure, thanks for your help
    $endgroup$
    – Jack
    Nov 11 '12 at 21:04
















3












$begingroup$


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







share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    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.
    $endgroup$
    – Inquest
    Nov 11 '12 at 20:19












  • $begingroup$
    Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
    $endgroup$
    – amWhy
    Nov 11 '12 at 21:01










  • $begingroup$
    amWhy: Sure, thanks for your help
    $endgroup$
    – Jack
    Nov 11 '12 at 21:04














3












3








3





$begingroup$


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







share|cite|improve this question











$endgroup$




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




linear-algebra linear-programming gaussian-elimination






share|cite|improve this question















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.8k41855




12.8k41855










asked Nov 11 '12 at 20:11









JackJack

336




336








  • 1




    $begingroup$
    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.
    $endgroup$
    – Inquest
    Nov 11 '12 at 20:19












  • $begingroup$
    Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
    $endgroup$
    – amWhy
    Nov 11 '12 at 21:01










  • $begingroup$
    amWhy: Sure, thanks for your help
    $endgroup$
    – Jack
    Nov 11 '12 at 21:04














  • 1




    $begingroup$
    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.
    $endgroup$
    – Inquest
    Nov 11 '12 at 20:19












  • $begingroup$
    Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
    $endgroup$
    – amWhy
    Nov 11 '12 at 21:01










  • $begingroup$
    amWhy: Sure, thanks for your help
    $endgroup$
    – Jack
    Nov 11 '12 at 21:04








1




1




$begingroup$
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.
$endgroup$
– Inquest
Nov 11 '12 at 20:19






$begingroup$
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.
$endgroup$
– Inquest
Nov 11 '12 at 20:19














$begingroup$
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
$endgroup$
– amWhy
Nov 11 '12 at 21:01




$begingroup$
Actually, I think the link is better, since I don't want to copy someone else's question without his/her permission.
$endgroup$
– amWhy
Nov 11 '12 at 21:01












$begingroup$
amWhy: Sure, thanks for your help
$endgroup$
– Jack
Nov 11 '12 at 21:04




$begingroup$
amWhy: Sure, thanks for your help
$endgroup$
– Jack
Nov 11 '12 at 21:04










2 Answers
2






active

oldest

votes


















0












$begingroup$

See my answer to this MO question.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    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).
    $endgroup$
    – Jack
    Nov 11 '12 at 20:46










  • $begingroup$
    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...
    $endgroup$
    – Jack
    Nov 11 '12 at 20:47



















0












$begingroup$

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









$endgroup$













    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
    });


    }
    });














    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















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    0












    $begingroup$

    See my answer to this MO question.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      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).
      $endgroup$
      – Jack
      Nov 11 '12 at 20:46










    • $begingroup$
      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...
      $endgroup$
      – Jack
      Nov 11 '12 at 20:47
















    0












    $begingroup$

    See my answer to this MO question.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      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).
      $endgroup$
      – Jack
      Nov 11 '12 at 20:46










    • $begingroup$
      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...
      $endgroup$
      – Jack
      Nov 11 '12 at 20:47














    0












    0








    0





    $begingroup$

    See my answer to this MO question.






    share|cite|improve this answer











    $endgroup$



    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 HuynhTony Huynh

    82057




    82057












    • $begingroup$
      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).
      $endgroup$
      – Jack
      Nov 11 '12 at 20:46










    • $begingroup$
      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...
      $endgroup$
      – Jack
      Nov 11 '12 at 20:47


















    • $begingroup$
      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).
      $endgroup$
      – Jack
      Nov 11 '12 at 20:46










    • $begingroup$
      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...
      $endgroup$
      – Jack
      Nov 11 '12 at 20:47
















    $begingroup$
    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).
    $endgroup$
    – Jack
    Nov 11 '12 at 20:46




    $begingroup$
    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).
    $endgroup$
    – Jack
    Nov 11 '12 at 20:46












    $begingroup$
    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...
    $endgroup$
    – Jack
    Nov 11 '12 at 20:47




    $begingroup$
    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...
    $endgroup$
    – Jack
    Nov 11 '12 at 20:47











    0












    $begingroup$

    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









    $endgroup$


















      0












      $begingroup$

      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









      $endgroup$
















        0












        0








        0





        $begingroup$

        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









        $endgroup$



        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









        littleOlittleO

        29.5k645109




        29.5k645109






























            draft saved

            draft discarded




















































            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.




            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















            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







            -

            Popular posts from this blog

            How to send String Array data to Server using php in android

            Image
            0 I have a String array which contains value string array = {6,37,38,837,7,...} and I have also used some string values. I want to send that all string values and string array to my database which is located at server side. When I am click on submit button the data will stored in table. On the PHP side I want to read this array as it is,other thing i will do at background means PHP side. See my below code then you will get it what I am says. Here is my code: public class Hotels extends Activity { // Declare Variables JSONArray jsonarray = null; private static final String TAG_ID = "id"; public static final String TAG_NAME = "name"; public static final String TAG_LOCATION = "location"; public static final String TAG_DESC = "description"; String f_date, l_date;...
            Read more

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

            Image
            up vote 5 down vote favorite 2 I would like to make it so that the vertical space below the title of each chapter is the same when using the Bjornstrup package (i.e. so that the descenders do not affect the spacing - as shown by the red arrow in the picture below). I think I'm fairly happy with the spacing around "A chapter", so I'd really like titles without descenders (e.g. "Contents") to have the same vertical spacing as "A chapter" below the title. I would also like to remove the large "0" in the contents title. Any help appreciated, as always. documentclass[11pt,a4paper]{book} % Packages[![enter image description here][1]][1] usepackage[left=3.5cm, right=3.5cm, top=4.3cm, bottom=4.25cm]{geometry} usepackage[utf8]{inputenc} usepackage{libertine} usepackage[libertine]{newtx...
            Read more

            Is anime1.com a legal site for watching anime?

            Image
            up vote 4 down vote favorite 1 Other anime streaming sites are blocking my IP because I'm Iranian while anime1.com isn't. I wanted to know if it's legal to watch/stream anime from this site. Thanks. anime-production share | improve this question edited Nov 27 at 22:38 W. Are 1,599 2 23 asked Nov 27 at 20:36 mhnajafi 23 3 add a comment ...
            Read more