Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 Gauss elimination to identify the redundant constraint.

Do you have any hints on this?

share|improve this question
1  
I'm not sure but you can find the rank of $C$ (of $Cx\geq d$) and then append the new constraint at the bottom of $C$ to form $C^*$ and find the rank of $C^*x\geq 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

2 Answers 2

See my answer to this MO question.

share|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
    
+1. ${{{{{}}}}}$ –  Tim Nov 11 '12 at 21:12

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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.