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$

2 Answers 2

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$
4
  • $\begingroup$ Your solution answers 'if and only if'. $\endgroup$
    – LinAlg
    Commented Jan 22, 2017 at 22:34
  • 2
    $\begingroup$ The English is ambiguous, but I read y3 can *only* be 1 if (condition) as such. $\endgroup$ Commented Jan 22, 2017 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
    Commented Jan 22, 2017 at 22:59
  • $\begingroup$ In your 2nd truth table, shouldn't the "unrestricted" be in the 2nd and 3rd rows? $\endgroup$ Commented Jan 23, 2017 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .