2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

I don't know why you find this surprising. Saying that a particular linear inequality $a x \le b$ is non-redundant is exactly the statement that the linear programming problem, maximize $a x$ subject to the other constraints, does not have an optimal solution with objective value $\le b$. Linear programming is the natural way to check this, especially given the availability of high-quality linear programming software.

$\endgroup$
1
$\begingroup$

A 2016 paper of Emeritus Professor H.P. Williams may be of interest . It follows a 1986 American Mathematical Monthly paper by the same author. It is based on Fourier - Motzkin Elimination. The reference is:

"The dependency diagram of a linear programme", Journal of the Operational Research Society (2016) 67, 450-456.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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