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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ As per first comment's pdf - in the pdf it is stated that heuristic method found more redundant constraints than LP method. Are those redundancies valid? Is LP the only method that guarantees that we will find all redundancies? Thanks. $\endgroup$
    – Bojan Vukasovic
    Commented Jan 16 at 22:34
  • $\begingroup$ @BojanVukasovic That would be a good question to ask the authors of the pdf. In principle, linear programming should find all redundant constraints, but roundoff errors could potentially mess things up. $\endgroup$
    – Robert Israel
    Commented Jan 17 at 18:20
4
$\begingroup$

Forgive me for reviving this post, but I felt I should point out that it is a theorem that the complexity of LP and the complexity of removing all redundant constraints is the same.

1997. Telgen, Jan. On Redundancy In Systems Of Linear Inequalities

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .