How do you find redundant constraints for a feasible region?

Question

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?

Answer 1

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$.

Answer 2

Suppose you have four non-redundant constraints. These define the feasible region (some sort of quadrilateral).

The fifth constraint is redundant if it does not intersect the feasible region - if it is non-redundant then adding it to the problem will trim off some part opf the feasible region.

For each of the earlier constraints, find where the fifth constraint would intersect the line. Test this point (against the other three constraints) to see if it is on the border of the feasible region. If it isn't for any of the earlier constraints, then it is redundant.