Is it valid to delete a constraint that is linear combination of other constraints?

Question

I have an optimization problem in which one constraint is linear combination of the other two constraints like this:

$$ (1) A+B \le D \\ (2) E+F \le D \\ (3) A+B+E+F \le 2D $$

Is it valid to delete constraint ${(3)}$, since it is a linear combination of constraints $(1)$ and $(2)$?

Answer 1

It is valid to delete constraint (3) since it is redundant with the other two. In some computer modelling languages, though, it can sometimes be useful to keep redundant constraints in the model to help reduce the search space.

Answer 2

You can only delete $(3)$. On the other hand, $(3)$ combined with either of them does not imply the third one.

Answer 3

To add a bit of formalism to the answer, we can think of the answer to this in terms of set relations. Let our initial feasible region be $$X =\{x \in \mathbb {R}^4|x_1 + x_2 \leq D, x_3 + x_4 \leq D,x_1 + x_2 +x_3+x_4\leq 2D\}$$ and the new feasible region be $$Y =\{x \in \mathbb {R}^4|x_1 + x_2 \leq D, x_3 + x_4 \leq D\}.$$ We want to know if $$X=Y.$$ Let us take any element $x \in X.$ It is immediate that it must also be in $Y$. Therefore, $$X \subseteq Y.$$ Now, take any element $y \in Y$. Can you show that it must also be in $X$? If you do that you've also shown $$Y \subseteq X.$$ These two results show that the feasible regions are identical.