# How do you find redundant constraints for a feasible region?

I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm only trying to find the non-redundant constraints that define a feasible region (i.e. I have no objective function), given a set of possibly redundant inequality constraints.

For instance, if I have:

$$0x_1 + x_2 \leq -1\\ 0x_1 - x_2 \leq -1\\ -x_1 + 0x_2 \leq -2\\ x_1 + 0x_2 \leq -2\\ x_1 + 0x_2 \leq -6$$

Is there a robust technique that could detect that the last constraint is redundant?

You could try maximizing $x_1 + 0 x_2$ subject to the first $5$ constraints. The constraint is redundant iff the optimal objective value $\le -6$.
• So, for $n$ constraints, I'd have to run an LP $n$ times? I was hoping to find a cheaper solution than that, if I can. – Nick Sweet Aug 24 '15 at 22:09