1

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!

highdimensionalbiology
  • 13
  • What is your definition of a redundant constraint? What if you pick each block equal to a single constraint? – LinAlg Jul 03 '18 at 18:52
  • If a block has one constraint it has no redundancy. Blocks must have at least 2 elements (I've updated the question to specify this). A constraint is redundant if, when removed, the feasible solution space stays exactly the same. Page 52 here has a less informal definition: https://www.inf.ethz.ch/personal/fukudak/lect/pclect/notes2014/PolyComp2014.pdf – highdimensionalbiology Jul 05 '18 at 17:08
  • Two observations. First, your pseudocode doesn't seem to address how you decide to divide into blocks (in order to conquer). Second, you may find some useful insights by looking into algorithms for dealing with dependent sets in matroids. – Ethan Bolker Jul 05 '18 at 17:15
  • if each block is the same, the property clearly does not hold – LinAlg Jul 05 '18 at 17:17
  • @EthanBolker I've added the block division approach to the assumptions (can be unequal) but typically I'd try to cut things into $n$ close-to-equal slices. – highdimensionalbiology Jul 05 '18 at 17:27
  • @LinAlg I agree that two independently nonredundant constraint parts can be totally redundant with one another; however, I'm specifying that we include a redundancy removal step whenever two parts are combined. – highdimensionalbiology Jul 05 '18 at 17:27

1 Answers1

0

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$.

LinAlg
  • 19,822
  • did you intend the third constraint to be x_1 >= 0.8? -1 -0.25 <= -1, -1 -4 <= -4, 1 0 <= -0.7 and -1 -0.5 <= -1.2, -1 0 <= 0. First two values are coefficients of x_1,x_2 – highdimensionalbiology Jul 06 '18 at 03:00
  • no, the counterexample works as-is; as for the grey part of your comment, the 1 in the -0.7 constraint should be -1, and I do not understand where -1.2 comes from – LinAlg Jul 06 '18 at 12:25