Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

Better tactics for removing redundant constraints than Linear Programming?

After reading:

Detection of Redundant Constraints

It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form

$$ Ax \le b$$

Short of some heuristic techniques.

I found this hard to believe, so I kept digging around and found:

https://www.emis.de/journals/HOA/MPE/Volume2010/723402.pdf

But what surprises me is that the techniques listed do NOT find ALL the redundant constraints, except linear programming itself.

So that gets me curious, do we not have any faster techniques of detecting ALL redundant constraints than linear programming?

I don't see this written anywhere explicitly, so I want to believe there exist quicker techniques, but i'm having difficulty finding anything on the internet.