0

For my class in OR I have to linearize the following constraint:

IF ($x_1$ = 0 AND $x_2$ = 0) THEN $x_3$ = 0.

My first idea was to make use of some binary variables ($y_1$, $y_2$ and $y_3$) and some sufficiently large integers ($M_1$ and $M_2$):

$x_1$ $\leq$ $M_1(1-y_1)$

$-x_1$ $\leq$ $M_1(1-y_1)$

$x_2$ $\leq$ $M_2(1-y_2)$

$-x_2$ $\leq$ $M_2(1-y_2)$

$x_3$ $\leq$ $M_3(2-y_2-y_3)$

$-x_3$ $\leq$ $M_3(2-y_2-y_3)$

However, using this constraints it can still be so that $x_1$ and $x_2$ are both 0 and $x_3$ is not zero.

Could someone please explain to me which part I'm missing?

wreitsma
  • 57
  • I forgot to mention that all $x_i$, i $\in {1,2,3}$ are real and unrestricted variables. – wreitsma Dec 03 '16 at 20:33
  • Are you looking for your answer to be expressed purely as a finite number of linear inequalities in the variables $x_1,x_2,x_3$ and perhaps a finite number of extra variables? If so, and the implication is the only relationship that should hold between the variables then I'm not sure it's possible using real numbers only. Even in the above, if $x_1$ is unrestricted then no matter what real number $M_1$ is you can pick $x_1$ so big such that $x_1 \leq M_1(1-y_1)$ is false.. unless $M_1 = x_1$ but then it's not linear anymore. – DAS Dec 03 '16 at 21:06
  • Are any of the variables upper or lower bounded by a real number(s)? It might also be possible if we are using extended real numbers and the convention that $0 \times \pm \infty = 0$. – DAS Dec 03 '16 at 21:09
  • I'm indeed looking for a solution that is expressed purely as a finite number of linear inequalities in the variables $x_1$, $x_2$, $x_3$ and perhaps a finite number of extra variables. The only restriction to the variables $x_1$, $x_2$, $x_3$ is that they should be real. Since there is nothing stated w.r.t. extended real numbers and the convention that $0 \cdot x \pm\infty = 0$, I suppose it is justified to use these. – wreitsma Dec 03 '16 at 21:36
  • linear in the $x_i$ variables only or linear in the $x_i$ variables and any additional variables? – DAS Dec 03 '16 at 23:44

1 Answers1

1

We need to encode unbounded variables and absolute values using inequalities. We will do this using the extended real numbers together with the definition used in measure theory that $0 \times \pm \infty = 0$. Using this system we have for all real numbers $t$ that $\pm \infty \times t = \pm \infty \times \mathrm{sgn}(t)$. We take as our system the following:

For all $i \in \{1,2\}$, $$x_i^{+}, x_i^{-} \geq 0$$ $$y_i^{+}, y_i^{-} \in \{0,1\}$$ $$x_i = x_i^{+} - x_i^{-}$$ $$y_i^{+} + y_i^{-} \leq 1$$ $$\infty \times x_i = \infty \times (y_i^{+} - y_i^{-})$$ $$\infty \times x_i^{+} = \infty \times y_i^{+}$$ $$\infty \times x_i^{-} = \infty \times y_i^{-}$$ Together with, $$- \infty \times (y_1^{+} + y_1^{-} + y_2^{+} + y_2^{-}) \leq x_3 \leq \infty \times (y_1^{+} + y_1^{-} + y_2^{+} + y_2^{-})$$

DAS
  • 732
  • First of all, thanks for your reaction. Second, your answer is obviously correct for the binary case, however, as mentioned above, I forgot to include the information that all $x_i$, i $\in {1,2,3}$ are real and unrestricted variables. Could you maybe rework your answer with this additional information? – wreitsma Dec 03 '16 at 20:34