# How to linearize the product of two binary variables?

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

• To generate more expected content for our new OR forum and since it is allowed to answers your own questions: I added this basic OR questions. see: stackoverflow.blog/2011/07/01/… – Michiel uit het Broek May 31 '19 at 6:16
• That's definitely the way to go. Especially while in beta. – ayhan May 31 '19 at 6:52
• I'd suggest an edit of the question. You actually answered the more general question how to linearize $x\cdot y$. The constraint $x\cdot y \le b$ can be eliminated in presolve: if $0\le b < 1$ then it implies $x=0=y$, and if $b\ge 1$ it does not constrain the binary variables $x$ and $y$ at all. – prubin Jun 5 '19 at 21:08
• @prubin edited :) – Michiel uit het Broek Jun 6 '19 at 2:19
• My guess is that within a year this will be the most valuable Q/A! We'll have to make it obvious to new users. – Michael Trick Jun 6 '19 at 3:04

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}

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.
• And in the general case, look at the McCormick relaxation. If someone is at CPAIOR next week, please write here anything of interest in Toby’s talk. – Edward Lam May 31 '19 at 13:33
• If you have a quadratic function of many binary variables, then you can often do better than to linearize each product of variables separately. I'll give some references in the next comment. – 4er Jun 2 '19 at 23:16
•  F Glover and E Woolsey, Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Operations Research 21 (1973) 156-161.  Glover, F. Improved Linear Integer Programming Formulations of Nonlinear Integer Problems. Management Science 22 (1975) 455-460.  M Oral and O Kettani, A linearization procedure for quadratic and cubic mixed-integer problems. Operations Research 40 (1992) S109-S116.  WP Adams and RJ Forrester, A simple recipe for concise mixed 0-1 linearizations. Operations Research Letters 33 (2005) 55-61. – 4er Jun 2 '19 at 23:16
• @4er is it oke if I add your paper suggestions to my answer such that they are better visible? Of course you will be mentioned :) – Michiel uit het Broek Jun 5 '19 at 8:52
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*}