# 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/… May 31 '19 at 6:16
• That's definitely the way to go. Especially while in beta. 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. Jun 5 '19 at 21:08
• @prubin edited :) 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. 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. 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 :) 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*}