4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ Dedection should either be Detection or Deduction. I'd guess Detection, but Deduction is also edit distance 1 from Dedection. $\endgroup$
    – Tony Huynh
    Commented Jul 6, 2011 at 22:05
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Commented Jul 6, 2011 at 22:39
  • 1
    $\begingroup$ Thank you for detecting the mistake and then deducing a correction. $\endgroup$
    – Countably Infinite
    Commented Jul 6, 2011 at 23:44

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I like the reformulation of redundancy as an implication. Do you think this is a "fast way" to do it? $\endgroup$
    – Countably Infinite
    Commented Jul 6, 2011 at 23:42
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented Jul 6, 2011 at 23:55
  • 1
    $\begingroup$ I want that t-shirt! $\endgroup$
    – Countably Infinite
    Commented Jul 7, 2011 at 11:08
  • 2
    $\begingroup$ The $c^T x \le d+1$ constraint is not needed. $\endgroup$
    – RobPratt
    Commented Aug 28, 2019 at 12:00
  • 2
    $\begingroup$ @independentvariable It is only there to rule out the possibility that the LP is unbounded. $\endgroup$
    – Tony Huynh
    Commented Oct 16, 2020 at 15:40

You must log in to answer this question.