How to reformulate or linearize the phrase "become redundant" or "not needed"?

Question

I am an electrical engineer and currently I have to deal with an optimization problem with a very specific requirement:

$\begin{array}{*{20}{c}} {\mathop {Min}\limits_x }&{f\left( x \right)}\\ {{c_1}:}&{{x_1} + {x_2} \ge 1}\\ {{c_2}:}&{{x_2} + {x_3} \ge 1}\\ {}&{{x_1},{x_2},{x_3} \in \left\{ {0,1} \right\}} \end{array}$

Particularly, there are some control variables $t_4$ and $t_5$ where ${t_4},{t_5} \in \left\{ {0,1} \right\}$ that literally state the following:

If $t_4=1$ then the constraint $c_1$ is needed to be kept. If $t_4=0$ then the constraint $c_1$ is not needed to be kept. In other words, $c_1$ becomes redundant and will not participate in the optimization process.

If $t_5=1$ then the constraint $c_2$ is needed to be kept. If $t_5=0$ then the constraint $c_2$ is not needed to be kept. In other words, $c_2$ becomes redundant and will not participate in the optimization process.

1/ How to linearize these statements and incorporate the corresponding variable $t_4$ and $t_5$ into the optimization problem ?

I am also not sure if we can exploit the fact that all of these variables are binary ${x_1},{x_2},{x_3},{t_4},{t_5} \in \left\{ {0,1} \right\}$ ?

Edited:

$\begin{array}{*{20}{c}} {\mathop {Min}\limits_x }&{f\left( x \right)}\\ {{c_1}:}&{{x_1} + {x_2} \ge 1}\\ {{c_2}:}&{{x_2} + {x_3} \ge 1}\\ {{c_3}:}&{{x_4} + {x_5} \ge {y_1}}\\ {{c_4}:}&{{x_5} + {x_6} \ge {y_2}}\\ {}&{{x_1},{x_2},{x_3} \in \left\{ {0,1} \right\}}\\ {}&{{y_1},{y_2} \in \left\{ {0,1} \right\}} \end{array}$

2/ I almost forgot about the case of constraint $c_3$ and $c_4$. Under this case how can we repeat the technique in question 1 for the two binary variable $t_6$, $t_7$ ?

If $t_6=1$ then the constraint $c_3$ is needed to be kept. If $t_6=0$ then the constraint $c_3$ is not needed to be kept. In other words, $c_3$ becomes redundant and will not participate in the optimization process.

Similarly for $t_7$, it is the same for $c_4$.

Thank you for your enthusiasm !

Answer 1

Your original constraint $c_1$ enforces the disjunction $x_1 \lor x_2$. That is, either $x_1=1 $ or $x_2=1$ (or both).

Your original constraint $c_3$ enforces the implication $y_1 \implies (x_4 \lor x_5)$. That is, if $y_1 = 1$ then either $x_4=1$ or $x_5=1$ (or both).

You can obtain the desired constraints somewhat automatically via conjunctive normal form.

For the first one: $$ t_4 \implies (x_1 \lor x_2) \\ \lnot t_4 \lor (x_1 \lor x_2) \\ \lnot t_4 \lor x_1 \lor x_2 \\ (1-t_4) + x_1 + x_2 \ge 1 \\ x_1 + x_2 \ge t_4 $$ It is easy to check the two cases:

• If $t_4=1$ then $x_1+x_2 \ge 1$, as desired.
• If $t_4=0$ then $x_1+x_2 \ge 0$, which is redundant.

For the third one: $$ (t_6 \land y_1) \implies (x_4 \lor x_5) \\ \lnot (t_6 \land y_1) \lor (x_4 \lor x_5) \\ (\lnot t_6 \lor \lnot y_1) \lor (x_4 \lor x_5) \\ \lnot t_6 \lor \lnot y_1 \lor x_4 \lor x_5 \\ (1-t_6) + (1-y_1) + x_4 + x_5 \ge 1 \\ x_4 + x_5 \ge t_6 + y_1 - 1 $$ It is easy to check the cases:

• If $t_6=y_1=1$, then $x_4+x_5 \ge 1$, as desired.
• If $t_6+y_1=1$, then $x_4+x_5 \ge 0$, which is redundant.
• If $t_6=y_1=0$, then $x_4+x_5 \ge -1$, which is redundant.

Answer 2

Replace $c_1$ with $c_1':x_1+x_2\geq t_4$. If $t_4=1$, you recover $c_1$; if $t_4=0$, the constraint becomes $x_1+x_2\geq 0$, which is redundant, since $x_1,x_2\in\{0,1\}$. Similarly, replace $c_2$ with $c_2':x_2+x_3\geq t_5$.