# Expressing Boolean constraint in binary integer linear programming

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.

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}

• Your solution answers 'if and only if'. – LinAlg Jan 22 '17 at 22:34
• The English is ambiguous, but I read y3 can *only* be 1 if (condition) as such. – Erwin Kalvelagen Jan 22 '17 at 22:49
• 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'. – LinAlg Jan 22 '17 at 22:59
• In your 2nd truth table, shouldn't the "unrestricted" be in the 2nd and 3rd rows? – Rodrigo de Azevedo Jan 23 '17 at 10:45

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.