2
$\begingroup$

Suppose we have three binary variables: $y_1$, $y_2$, and $y_3$. We want to enforce the following using one or more linear constraints:

$$ y_3 \text{ can only be 0 if exactly one of } y_1, y_2 \text{ is 1.}$$

How to do this? We can only add extra auxilliary binary variables.

$\endgroup$
5
$\begingroup$

This can be described as a set of linear inequalities: $$\begin{align} &y_3\ge 1-y_1-y_2\\ &y_3\le 1-y_1+y_2\\ &y_3\le 1-y_2+y_1\\ &y_3\ge y_1+y_2-1 \end{align}$$

These inequalities implement $y_1+y_2=1 \Leftrightarrow y_3=0$

Update

This is the "if then else" case, it follows the truth table:

$$ \begin{matrix} &y_1&y_2&y_3\\ &0 & 0& 1\\ &0 & 1& 0\\ &1 & 0& 0\\ &1 & 1& 1 \end{matrix} $$

If you only want the "if then" part, i.e. $y_1+y_2=1 \Rightarrow y_3=0$, with $$ \begin{matrix} &y_1&y_2&y_3\\ &0 & 0& \text{unrestricted}\\ &0 & 1& 0\\ &1 & 0& 0\\ &1 & 1& \text{unrestricted} \end{matrix} $$ you can use: $$\begin{align} &y_3\le 1-y_1+y_2\\ &y_3\le 1-y_2+y_1 \end{align}$$

You may actually mean: $y_1+y_2\ne 1 \Rightarrow y_3 \ne 0$:

$$ \begin{matrix} &y_1&y_2&y_3\\ &0 & 0& 1\\ &0 & 1& \text{unrestricted}\\ &1 & 0& \text{unrestricted}\\ &1 & 1& 1 \end{matrix} $$ then just use:

$$\begin{align} &y_3\ge 1-y_1-y_2\\ &y_3\ge y_1+y_2-1 \end{align}$$

$\endgroup$
  • $\begingroup$ Your solution answers 'if and only if'. $\endgroup$ – LinAlg Jan 22 '17 at 22:34
  • 1
    $\begingroup$ The English is ambiguous, but I read y3 can *only* be 1 if (condition) as such. $\endgroup$ – Erwin Kalvelagen Jan 22 '17 at 22:49
  • $\begingroup$ Ah yes, two ways to interpret it: (1) if (condition) then $y_3=0$, (2) if $y_3=0$ then (condition). From your comment I think you read it as (1), but your answer is still 'if and only if'. $\endgroup$ – LinAlg Jan 22 '17 at 22:59
  • $\begingroup$ In your 2nd truth table, shouldn't the "unrestricted" be in the 2nd and 3rd rows? $\endgroup$ – Rodrigo de Azevedo Jan 23 '17 at 10:45
1
$\begingroup$

I interpret the statement

$$ y_3 \text{ can only be } 0 \text{ if exactly one of } y_1, y_2 \text{ is } 1 $$

as follows

$$\begin{array}{cc|c} y_1 & y_2 & y_3\\ \hline 0 & 0 & 1\\ 0 & 1 & \#\\ 1 & 0 & \#\\ 1 & 1 & 1\end{array}$$

where the symbol $\#$ stands for "unconstrained". Hence,

$$y_3 \geq \begin{cases} 1 & \text{if } (y_1, y_2) = (0, 0)\\ 0 & \text{if } (y_1, y_2) = (0, 1)\\ 0 & \text{if } (y_1, y_2) = (1, 0)\\ 1 & \text{if } (y_1, y_2) = (1, 1)\end{cases}$$

One possibility would be

$$y_3 \geq | 1 - y_1 - y_2 | = \max \left\{ 1 - y_1 - y_2, -1 + y_1 + y_2 \right\}$$

which produces the two linear inequalities

$$y_1 + y_2 + y _3 \geq 1$$

$$-y_1 - y_2 + y _3 \geq -1$$

where $0 \leq y_1, y_2, y_3 \leq 1$. Note that this is what Erwin proposed in his answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.