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?
Best Answer
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$.