1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nick Sweet Aug 24 '15 at 22:09
  • $\begingroup$ May be you could try the more efficient method of Clarkson as given in inf.ethz.ch/personal/fukudak/lect/pclect/notes2014/…, see page 55. By the way, in section 8.1 it is shown that a single redundancy check is as hard as linear programming. $\endgroup$ – Willem Hagemann Aug 26 '15 at 11:32
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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