# Removing linear redundant constraints using Gauss 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 Gauss elimination to identify the redundant constraint.

Do you have any hints on this?

-
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

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

-