Background The distributive property for multiplication with addition is $a(b + c) = ab + ac$. So we can think of a as a function f that takes in a number, and outputs the result multiplied by a.
$f(input) ==> a*input$
Does this property hold with redundancy removal across linear inequality constraints?
With a system of linear inequalities, let's say we split the constraints into $n$ separate parts, and remove all redundant constraints within the $n$ sections, only checking within each section. Then after vertically concatenating the non-redundant parts, we run redundancy elimination on the rest. Importantly, I do not aim to extract an optimum, so constraints must be redundant across the entire space of x that correctly yields b.
Assume
1. redundancyRemover($A$,$b$) ==> A',b' in $O(r^2)$ time, where r is the number of constraints (i.e. the number of rows of A). One such algorithm exists in the section starting on page 54 of https://www.inf.ethz.ch/personal/fukudak/lect/pclect/notes2014/PolyComp2014.pdf.
2. $ x, A, b are real numbers, not integers.
3. We assume random order of the constraints prior to splitting.
4. Parts always have at least 2 elements.
5. Parts can have unequal lengths.
$Ax \leq b$
turns into
$A_1x_1 \leq b_1 \\ A_2x_2 \leq b_2 \\ ...$
and all parts are fed through the redundancy checker
($A_1',b_1'$) = redundancyRemover($A_1, b_1$)
($A_2',b_2'$) = redundancyRemover($A_2, b_2$)
($A_3',b_3'$) = redundancyRemover(...)
and finally the concatenated result has its redundancy removed as well:
\begin{bmatrix} A_1'\\ A_2'\\ A_3'\\ \end{bmatrix} and \begin{bmatrix} b_1'\\ b_2'\\ b_3'\\ \end{bmatrix}
producing $A',b'$.
is redundancyRemover($A,b$) == redundancyRemover($A',b'$) ?
Edits:
1. Only sections that have 2 or more constraints can be evaluated for redundancies. A section with one constraint would 'pass' with no redundancies.
2. Assumptions 3-5 added to define how parts are split.
3. Specified that no cost functions are used in the computation of redundancy.
References I've been looking through to try to find a proof/intuitive logic:
Here's a question that looks at this visually: identifying if constraints are binding, non binding or redundant visually
And another post where they mention using one LP to test a particular solution across all others. How do you find redundant constraints for a feasible region?
Here are some of the algorithms for redundancy removal, but as far as I can tell the output will be the same: Ray shooting: https://www.inf.ethz.ch/personal/fukudak/lect/pclect/notes2014/PolyComp2014.pdf
8.2 H Redundancy Removal: https://www.inf.ethz.ch/personal/fukudak/lect/pclect/notes2014/PolyComp2014.pdf
thank you!
The answer is negative, consider $$\min\{x_1 + x_2 : x \in A, x \in B\}$$ with $$A = \{x : x_1 \geq 1-0.25 x_2, x_1 \geq 4-4x_2, x_1 \geq 0.7\}$$ $$B = \{x : x_1 \geq 10 - 0.5 x_2, x \geq 0 \}.$$ In $A$, the last constraint is redundant since the optimum is at $(0.8,0.8)$. However, for the full problem the optimal solution is $(0.7,18.6)$, which depends on the last constraint in $A$.