How to linearize the product of two binary variables?

Question

Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?

Answer 1

This scenario can be linearized by introducing a new binary variable $z$ which represents the value of $x y$. Notice that the product of $x$ and $y$ can only be non-zero if both of them equal one, thus $x = 0$ and/or $y = 0$ implies that $z$ must equal zero.

$$z \leq x\\z \leq y$$

The only thing left is to force $z$ to equal one if the product of $x$ and $y$ equals one, which only happens if both of them equal one.

$$ z \geq x + y - 1. $$

The general case with $n$ binary variables

This method can also directly be applied to the general case where we have the product of multiple binary variables. Suppose we have $n$ binary variables $x_i$ and we want to linearize the product $$ \prod_{i=1}^n x_i. $$ Then you can introduce a new binary variable $z$ that represents the value of this product and model it by introducing the following constraints $$ \begin{align} z &\leq x_i \quad \text{ for } i = 1, \ldots, n.\\ z &\geq \sum_{i=1}^n x_i - (n-1). \end{align} $$

Further reading

As mentioned by 4er in a comment below this answer: "for quadratic functions of many binary variables, you can often do better than to linearize each product of variables separately". Some suggested references are:

1. F. Glover and E. Woolsey (1973). Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Operations Research 21 156-161.
2. F. Glover (1975). Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science 22 455-460.
3. M. Oral and O. Kettani (1992). A linearization procedure for quadratic and cubic mixed-integer problems. Operations Research 40 S109-S116.
4. W.P. Adams and R.J. Forrester (2005). A simple recipe for concise mixed 0-1 linearizations. Operations Research Letters 33 55-61.

Answer 2

It is worth noting that this formulation can be derived somewhat automatically by writing the logical proposition in conjunctive normal form: \begin{align*} & z \iff x \wedge y \\ & \left(z \implies (x \wedge y)\right) \bigwedge \left((x \wedge y) \implies z\right) \\ & \left(\neg z \vee (x \wedge y)\right) \bigwedge \left(\neg(x \wedge y) \vee z\right) \\ & \left((\neg z \vee x) \wedge (\neg z \vee y)\right) \bigwedge \left((\neg x \vee \neg y) \vee z\right) \\ & (\neg z \vee x) \bigwedge (\neg z \vee y) \bigwedge (\neg x \vee \neg y \vee z) \\ & \left((1 - z) + x \ge 1\right) \bigwedge \left((1 - z) + y \ge 1\right) \bigwedge \left((1 - x) + (1 - y) + z \ge 1\right) \\ & (x \ge z) \bigwedge (y \ge z) \bigwedge (z \ge x + y - 1) \end{align*}

Answer 3

As the first answer:

$$ \begin{align} z &\leq x_i \quad \forall i = 1, \ldots, n.\\ z &\geq \sum_{i=1}^n x_i - (n-1). \end{align} $$

We should note that, the property holds for an aggregated version of these constraints (obtained from the sum of the $z \leq x_i \quad \forall i = 1, \ldots, n$.

$$ \begin{align} n.z & \leq \sum_{i=1}^{n} x_i \\ z & \geq \sum_{i=1}^n x_i -(n-1) \end{align} $$

I prefer to use less constraints.