1

Is there a method for testing if one system of linear inequalities implies another one? For example, consider systems A and B:

A: x + y <= z
B: x <= z
   y <= z

If all variables are constrained to be non-negative (typical in LP), then intuition suggests that system A implies system B. That is, any solution of A is also a solution of B. (The converse is not true.) In matrix form, we have:

A: 1x + 1y + (-1)z <= 0
B: 1x + 0y + (-1)z <= 0
   0x + 1y + (-1)z <= 0

A: [ 1  1  -1 ] [ 0 ]
B: [ 1  0  -1 ] [ 0 ]
   [ 0  1  -1 ] [ 0 ]

I have come up with one way to test if implication holds, but I find it unsatisfactory. This approach is to understand it as ¬A ∨ B. Dealing negation and disjunction generally requires a Big-M conversion. For what I'm trying to do, Big-M conversion has two serious drawbacks:

  1. Can be difficult or impossible to find an upper bound
  2. The introduction of binary variables moves us from LP to MIP

So my question is whether or not there is a better technique for testing whether or not A implies B.

EDIT:

Some more of my own thoughts on this. In the restricted setting where all of the same variables appear in A and B, a visual representation of this problem is testing if a convex polygon (or polyhedra, etc.) contains another one.

I have found a similar question Detection of Redundant Constraints, but I am not sure if the answer is connected to my question.

Andrew Thaddeus Martin
  • 111
  • 2
    If you're testing if the intersection of solutions of $A$ and $B$ is nonempty, then this is solved as a feasibility problem, i.e. an LP with $0$ objective function and all the inequalities combined. Testing containment is trickier, but essentially testing if each inequality in $B$ is redundant should do the trick, see this. – V.S.e.H. Jul 07 '23 at 17:00
  • 1
    Related https://math.stackexchange.com/a/2097261/443030 – V.S.e.H. Jul 07 '23 at 17:17

0 Answers0