Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I pose the following query to a constraint logic programming system:

?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3.

Are there systems that would recognize the last inequality as redundant and remove?

The problem is especially annoying since in contrast to equality equations there is no upper bound on the number of independent constraints. But nevertheless it might happen in linear inequalities that one constraint is made redundant by others.

Any fast way to detect the situation?

Bye

share|improve this question
    
Dedection should either be Detection or Deduction. I'd guess Detection, but Deduction is also edit distance 1 from Dedection. –  Tony Huynh Jul 6 '11 at 22:05
    
given the question in the last sentence, i edited the title. i also added the tag 'linear-programming'---I hope you are ok with it. –  Suvrit Jul 6 '11 at 22:39
1  
Thank you for detecting the mistake and then deducing a correction. –  Countably Infinite Jul 6 '11 at 23:44
add comment

1 Answer 1

This can be done via linear programming. Consider a set of linear inequalities $Ax \leq b$, together with an additional inequality $c^Tx \leq d$. We wish to know if the constraint $c^Tx \leq d$ is redundant.

Consider the linear program:

$\max c^Tx$ subject to

$Ax \leq b$,

$c^T x \leq d+1$.

The constraint $c^Tx \leq d$ is implied by $Ax \leq b$ if the above linear program has optimal value at most $d$.

In the degenerate case that the above LP is infeasible, then $c^Tx \leq d$ is redundant if and only if $Ax \leq b$ is infeasible.

share|improve this answer
    
I like the reformulation of redundancy as an implication. Do you think this is a "fast way" to do it? –  Countably Infinite Jul 6 '11 at 23:42
    
Linear programming is "fast" (in practice) so I'd say yes. Also, by testing each constraint for redundancy one at a time, we can get down to a "minimal" system. If what you really care about is getting down to a minimal system, I'd guess there is a slicker way. But if you want to test if a particular constraint is redundant, I can't think of anything that would be much faster. –  Tony Huynh Jul 6 '11 at 23:55
1  
I want that t-shirt! –  Countably Infinite Jul 7 '11 at 11:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.