Linearizing product of binary variables

Question

How would I linearize the following expression

$$ z = (1-x)y $$

where $x,y \in \{0,1\}$? Ideally, I would want to formulate this as a system of linear inequalities.

Answer 1

$(1-x)$ is just swapping $0$ and $1$. so without changing the problem consider $\bar{x}=1-x$ as our binary variable. $$ z = \bar{x}y \qquad \bar{x},y \in \{0,1\} $$ so logically this means: $$ z \equiv \bar{x} \land y. \tag{1} $$ $\bar{x}$ and $y$ are our independent variables so (1) chronologically means : $$ \bar{x}=0 \lor y=0 \Rightarrow z=0 \\ \bar{x}=1 \land y=1 \Rightarrow z=1 $$ you can linearize these by introducing binary variable $\gamma$ with additional three constraints: $$ z = \gamma \\ \gamma \leq \bar{x} \\ \gamma \leq y \\ \bar{x}+y \leq \gamma +1 . $$ you can easily check that this works. if for example $\bar{x}=0$ then by second constraint $\gamma=0$. third and fourth constraint become redundant. (also similar for $y=0$). and of $\bar{x}=y=1$ then by fourth constraint $\gamma=1$.